数据结构、算法与应用-C++描述13.ppt

* * 给出有向图G，它的每条边都有一个非负的长度（耗费） a [i][j]，路径的长度即为此路径所经过的边的长度之和。 对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。 单源最短路问题 * * 单源最短路问题 * * 利用E. Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。 每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。 也就是说，Dijkstra的方法按路径长度顺序产生最短路径。 单源最短路问题贪婪策略 * * 首先最初产生从s到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。 一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。 另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些路径中先选择最短的，这种策略即是Dijkstra算法。 分析 * * 可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。 实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。 分析 * * 单源最短路问题 * * 可用一种简便的方法来存储最短路径。可以利用数组p，p[i]给出从s到达i的路径中顶点i前面的那个顶点。在本例中p[1:5]=[0,1,1,3,4]。从s到顶点i的路径可反向创建。从i出发按p[i],p[p[i]],p[p[p[i]]],…的顺序，直到到达顶点s或0。 在本例中，如果从i=5开始，则顶点序列为p[i]=4,p[4]=3,p[3]=1=s，因此路径为1,3,4,5。 分析 * * 为能方便地按长度递增的顺序产生最短路径，定义d[i]为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s到s的一条长度为0的路径，这时对于每个顶点i，d[i]等于a[s][i]（a是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。 算法分析 * * 1)初始化d[i]=a[s][i]（1≤i≤n）， 对于邻接于s的所有顶点i，置p[i]=s,对于其余的顶点置p[i]=0； 对于p[i]≠0的所有顶点建立L表。 2)若L为空，终止，否则转至3)。 3)从L中删除d值最小的顶点-i。 4)对于与i邻接的所有还未到达的顶点j，更新d[j]值为min{d[j],d[i]+a[i][j]}；若d[j]发生了变化且j还未在L中，则置p[j]=i，并将j加入L，转至2。 最短路径算法的描述 * * templateclass T void AdjacencyWDigraphT:: ShortestPaths(int s,T d[],int p[]) {//寻找从顶点s出发的最短路径,在d中返回最短距离，在p中返回前继顶点 if(s1||sn)throw OutOfBounds(); Chainint L;//路径可到达顶点的列表 ChainIteratorint I; //初始化d,p,L for(int i=1;i=n;i++){ d[i]=a[s][i]; if(d[i]==NoEdge)p[i]=0; else{ p[i]=s; L.Insert(0,i);} } 最短路径程序 * * //更新d,p while(!L.IsEmpty()){ //寻找具有最小d的顶点v int *v=I.Initialize(L); int *w=I.Next(); while(w){ if(d[*w]d[*v]) v=w; w=I.Next(); } 最短路径程序 * * //从L中删除通向顶点v的下一最短路径并更新d int i=*v; L.Delete(*v); for(int j=1;j=n;j++){ if(d[j]d[i]+a[i][j])){ //减小d[j] d[j]=d[i]+a[i][j]; //将j加入L if(!p[j])L.Insert(0,j); p[j]=i;} } } } 最短路径程序 * * 若图是连通的无向图或强连通的有向图，则从其中任何一个顶点出发都可以系统地访问到图中所有的顶点。 图的所有顶点加上遍历过程中经