1、1第第14章章 最短路径问题最短路径问题 单源最短路径单源最短路径 所有顶点对间的最短路径所有顶点对间的最短路径2单源最短路径单源最短路径非加权图的最短路径非加权图的最短路径 加权图的最短路径加权图的最短路径 带有负权值的图带有负权值的图无环图无环图给出一个加权图和图上的一个节点给出一个加权图和图上的一个节点s s，找出，找出s s到图中到图中每一节点的最短路径每一节点的最短路径3非加权的最短路径非加权的最短路径 采用广度优先搜索，它按层处理一层的所有采用广度优先搜索，它按层处理一层的所有结点：离起始结点最近的结点最先处理，距结点：离起始结点最近的结点最先处理，距离最远的最晚处理。离最远的最晚
2、处理。具体过程：具体过程：从从s s到到s s的最短路径为的最短路径为0 0通过搜索通过搜索S S的所有邻接结点就能找到离的所有邻接结点就能找到离S S距离为距离为1 1的所有结点的所有结点搜索离搜索离S S距离为距离为1 1的所有结点的邻接结点就能找的所有结点的邻接结点就能找到距离为到距离为2 2的节点的节点重复上述过程，直到所有节点都访问到为止重复上述过程，直到所有节点都访问到为止4找找v2到其他节点的最短距离到其他节点的最短距离V2V0V5V1V3V4V60V2V0V5V1V3V4V6011V2V0V5V1V3V4V601122V2V0V5V1V3V4V601122335存储设计存储设计
3、 数组数组distancedistance：记录从源点到达每个结点的最短：记录从源点到达每个结点的最短距离。距离。数组数组prevprev：记录要到达此结点，必须到达的前一：记录要到达此结点，必须到达的前一结点。结点。例如，对于上图中的结点例如，对于上图中的结点v4v4，prevv4prevv4记录的是记录的是v1v1。也就是说，从源点到达。也就是说，从源点到达v4v4必须先到必须先到v1v1。而。而prevv1prevv1记录的是记录的是v0v0，prevv0prevv0记录的是记录的是v2v2。从。从prevprev数组，我们可以追溯到这条路径。例如，对数组，我们可以追溯到这条路径。例如，
4、对于于v4v4，我们可以追溯到这条路径为，我们可以追溯到这条路径为v2-v0-v1-v4v2-v0-v1-v4。6过程抽象过程抽象unweightedShortDistance(start)for（每个结点（每个结点v）distancev=无穷大；无穷大；distancestart=0;prevstart=0;for(int curDistance=0;curDistance 结点数结点数;+curDistance)for(每个结点每个结点u)if(distanceu=curDistance)for(u的每一个邻接点的每一个邻接点v)if（distancev=无穷大）无穷大）distancev
5、=curDistanve+1；prevv=u；.7分析分析 算法的时间复杂度为算法的时间复杂度为O O（|V|E|V|E|）。）。算法效率之所以低的原因之一在于：为保算法效率之所以低的原因之一在于：为保证所有结点都找到了最短路径，算法假设证所有结点都找到了最短路径，算法假设最长的路径是经过所有的结点。最长的路径是经过所有的结点。该算法效率之所以低的第二个原因在于：该算法效率之所以低的第二个原因在于：内层循环的设计。在处理距离为内层循环的设计。在处理距离为d d的结点时，的结点时，我们找到了所有距离为我们找到了所有距离为d+1d+1的结点。但算法的结点。但算法并没有利用这个成果，而在下一个循环周
6、并没有利用这个成果，而在下一个循环周期中又用顺序查找的方法检查了所有结点，期中又用顺序查找的方法检查了所有结点，从中挑出距离为从中挑出距离为d+1d+1的结点。这浪费了大量的结点。这浪费了大量的时间。的时间。8算法的改进算法的改进 外层循环没必要执行外层循环没必要执行|V|V|次，只要所有的次，只要所有的结点都已找到了最短距离就可以了。结点都已找到了最短距离就可以了。第二层循环也没必要执行第二层循环也没必要执行|V|V|次，只要检次，只要检查新找到最短路径的结点。用一个队列查新找到最短路径的结点。用一个队列保存新找到路径的结点保存新找到路径的结点9改进算法的伪代码改进算法的伪代码unweigh
7、tedShortDistance(start)for（每个结点（每个结点v）distance(v)=无穷大；无穷大；distancestart=0;start入队入队;while （队列非空）（队列非空）取出队头元素存入取出队头元素存入u；for(u的每一个邻接点的每一个邻接点v)if（distancev=无穷大）无穷大）distancev=distanceu+1；prevv=u；v入队；入队；.10邻接表中的实现邻接表中的实现template void adjListGraph :unweightedShortDistance (TypeOfVer start,TypeOfEdge noEd
8、ge)const linkQueue q;TypeOfEdge*distance=new TypeOfEdgeVers;int*prev=new int Vers;int u,sNo;edgeNode*p;for(int i=0;i Vers;+i)distancei=noEdge;11/寻找起始结点的编号寻找起始结点的编号 for(sNo=0;sNo Vers;+sNo)if(verListsNo.ver=start)break;if(sNo=Vers)cout 起始结点不存在起始结点不存在 next)if(distancep-end=noEdge)distancep-end=distanc
9、eu+1;prevp-end=u;q.enQueue(p-end);/输出最短路径输出最短路径 for(i=0;i Vers;+i)cout 从从 start 到到 verListi.ver 的路径为的路径为:endl;printPath(sNo,i,prev);cout endl;12队列的变化：队列的变化：2 d2=00 5 d0=1,d5=15 1 3 d1=2,d3=21 33 4 d4=34 6 d6=36空空 算法结束算法结束V2V0V5V1V3V4V613printPath函数的实现函数的实现 路径的存储不是正向的。即可以从第一个路径的存储不是正向的。即可以从第一个结点找到第二个
10、结点，从第二个结点找到结点找到第二个结点，从第二个结点找到第三个结点，第三个结点，。而是逆向存储的，即。而是逆向存储的，即最后一个结点记住倒数第二个结点，倒数最后一个结点记住倒数第二个结点，倒数第二个结点记住倒数第三个结点，第二个结点记住倒数第三个结点，。适合用递归处理。于是我们定义了一个私适合用递归处理。于是我们定义了一个私有的递归成员函数有的递归成员函数printPathprintPath来输出这条路来输出这条路径。径。14template void adjListGraph :printPath(int start,int end,int prev)const if(start=end)
11、cout verListstart.ver;return;printPath(start,prevend,prev);cout -verListend.ver;15函数的输出函数的输出从从v2到到v0的路径为：的路径为：v2 v0从从v2到到v1的路径为：的路径为：v2 v0-v1从从v2到到v2的路径为：的路径为：v2从从v2到到v3的路径为：的路径为：v2 v0 v3从从v2到到v4的路径为：的路径为：v2 v0 v3 v4从从v2到到v5的路径为：的路径为：v2 v5从从v2到到v6的路径为：的路径为：v2 v0 v3 v6 V2V0V5V1V3V4V616时间复杂度时间复杂度 算法的主
12、体是算法的主体是whilewhile循环，该循环一直执行到队循环，该循环一直执行到队列为空。而图中的每个结点都必须而且仅入队一列为空。而图中的每个结点都必须而且仅入队一次，因此该循环必须执行次，因此该循环必须执行|V|V|个循环周期。个循环周期。每个循环周期检查出队结点的所有边，整个每个循环周期检查出队结点的所有边，整个whilewhile循环检查了图中所有的边。因此，循环检查了图中所有的边。因此，whilewhile循循环的运行时间为环的运行时间为O O（|E|E|）。前面的一些辅助工作，）。前面的一些辅助工作，如初始化、寻找起始结点的编号等所需要的时间如初始化、寻找起始结点的编号等所需要的
13、时间是是O O（|V|V|）。所以算法的总运行时间为）。所以算法的总运行时间为O O（|V|+|E|V|+|E|）。）。17单源最短路径单源最短路径非加权图的最短路径非加权图的最短路径 加权图的最短路径加权图的最短路径 带有负权值的图带有负权值的图无环图无环图给出一个加权图和图上的一个节点给出一个加权图和图上的一个节点s s，找出，找出s s到图中到图中每一节点的最短路径每一节点的最短路径18Dijkstra算法算法 保存了一个顶点集保存了一个顶点集S S。S S中的顶点是已经找到了最短路径的中的顶点是已经找到了最短路径的顶点。顶点。开始时，顶点集合开始时，顶点集合S S只包含源点一个顶点。只
14、包含源点一个顶点。反复执行以下循环，直至顶点集反复执行以下循环，直至顶点集S S 包含所有的顶点为止：包含所有的顶点为止：对于在顶点集对于在顶点集V-SV-S中的每个顶点，考察新加入顶点集中的每个顶点，考察新加入顶点集S S中中的结点是否有边到达自己。如果存在，则检查这条路径是的结点是否有边到达自己。如果存在，则检查这条路径是否比原来已知的路径要短。如果是，则更新源点到此结点否比原来已知的路径要短。如果是，则更新源点到此结点的距离和路径；然后，从的距离和路径；然后，从V V S S中寻找一个路径最短的结中寻找一个路径最短的结点，从源点到这个结点已经不可能有更好的路径了，把它点，从源点到这个结点
15、已经不可能有更好的路径了，把它加入顶点集加入顶点集S S194V2V0V5V1V3V4V6421253102481654V2V0V5V1V3V4V642125310248165654V2V0V5V1V3V4V642125310248165654V2V0V5V1V3V4V6421253102481656579204V2V0V5V1V3V4V64212531024816565794V2V0V5V1V3V4V64212531024816565794V2V0V5V1V3V4V642125310248165657921存储设计存储设计 和非加权图的实现中一样，需要保存的和非加权图的实现中一样，需要保存的
16、距离和路径信息距离和路径信息 还需要保存哪些结点在还需要保存哪些结点在S S中，哪些结点不中，哪些结点不在在S S中的信息。中的信息。设计三个数组：设计三个数组：distance、prev和和known，22伪代码伪代码void dijkstra(start)for（图中的每个顶点（图中的每个顶点v）distancev=INFINITY;knownv=false;distancestart=0;for(i=1;i Vers;+i)v=所有所有known标记为标记为false的结点中的路径最短者；的结点中的路径最短者；knownv=true;for（v的每一个邻接点的每一个邻接点w）if(kno
17、wnw 等于等于false&distancev+(v,w)的权值的权值 distancew)distancew=distancev+(v,w)的权值的权值 Prevw=v;23邻接表类中实现的邻接表类中实现的Dijkstra算法算法 template void adjListGraph :dijkstra(TypeOfVer start,TypeOfEdge noEdge)const TypeOfEdge*distance=new TypeOfEdgeVers;int*prev=new int Vers;bool*known=new boolVers;int u,sNo,i,j;edgeNod
18、e*p;TypeOfEdge min;for(i=0;i Vers;+i)/初始化初始化 knowni=false;distancei=noEdge;24for(sNo=0;sNo Vers;+sNo)if(verListsNo.ver=start)break;if(sNo=Vers)cout 起始结点不存在起始结点不存在 endl;return;distancesNo=0;prevsNo=sNo;for(i=1;i Vers;+i)min=noEdge;for(j=0;j Vers;+j)if(!knownj&distancej next)if(!knownp-end&distancep-e
19、nd min+p-weight)distancep-end=min+p-weight;prevp-end=u;for(i=0;i Vers;+i)/输出所有的路径信息输出所有的路径信息 cout 从从 start 到到 verListi.ver 的路径为的路径为:endl;printPath(sNo,i,prev);cout t长度为：长度为：distancei endl;25执行执行dijkstra函函数的过程数的过程：源：源点为点为v1udist 0prev0known0dist 1prev1known1dist 2prev2known2dist3prev3known3dist 4prev
20、4known4dist 5prev5known5dist 6prev6known6,-,F0,1,F,-,F,-,F,-,F,-,F,-,F1,-,F0,1,T,-,F3,1,F10,1,F,-,F,-,F3,-,F0,1,T5,3,F3,1,T5,3,F11,3,F7,3,F29,2,F0,1,T5,3,T3,1,T5,3,F10,2,F7,3,F49,2,F0,1,T5,3,T3,1,T5,3,T10,2,F7,3,F69,2,F0,1,T5,3,T3,1,T5,3,T8,6,F7,3,T59,2,F0,1,T5,3,T3,1,T5,3,T8,6,T7,3,TV2V0V5V1V3V4V64
21、21253102481626输出结果输出结果从从v1到到v0的路径为：的路径为：v1 v3 v2-v0 长度为：长度为：9从从v1到到v1的路径为：的路径为：v1 长度为：长度为：0从从v1到到v2的路径为：的路径为：v1 v3 v2 长度为：长度为：5从从v1到到v3的路径为：的路径为：v1 v3 长度为：长度为：3从从v1到到v4的路径为：的路径为：v1 v3 v4 长度为：长度为：5从从v1到到v5的路径为：的路径为：v1 v3 v6-v5 长度为：长度为：8从从v1到到v6的路径为：的路径为：v1 v3 v6 长度为：长度为：727时间复杂度时间复杂度 Dijkstra Dijkstr
22、a 算法运行时间主要由两部分组成：算法运行时间主要由两部分组成：查找路径最短的尚未在查找路径最短的尚未在S S中的结点中的结点u u，以及扫，以及扫描描u u的邻接点，更新他们的距离。的邻接点，更新他们的距离。每次找出距离最短的结点所需的时间是每次找出距离最短的结点所需的时间是O(|V|)O(|V|)，在整个算法的执行过程中，寻找距，在整个算法的执行过程中，寻找距离最短的结点将花去离最短的结点将花去O(|V|O(|V|2 2)的时间。的时间。更新更新V-SV-S中的结点的距离所需的时间是中的结点的距离所需的时间是O(|E|)O(|E|)总的时间复杂度是总的时间复杂度是O(|E|+|V|O(|E
23、|+|V|2 2)=O(|V|)=O(|V|2 2)28单源最短路径单源最短路径非加权图的最短路径非加权图的最短路径 加权图的最短路径加权图的最短路径 带有负权值的图带有负权值的图无环图无环图给出一个加权图和图上的一个节点给出一个加权图和图上的一个节点s s，找出，找出s s到图中到图中每一节点的最短路径每一节点的最短路径29带有负权值的图带有负权值的图 如果一个图带有负权值的边，如果一个图带有负权值的边，DijkstraDijkstra算法无法正常工作算法无法正常工作V2V0V5V1V3V4V64212331024-816如按如按Dijkstra算法，从结算法，从结点点2出发首先会认为结点出
24、发首先会认为结点5是已知节点，但事实上，是已知节点，但事实上，2-0-3-5是一条更短的路径。是一条更短的路径。30一个直观的解决方案一个直观的解决方案 对每条边的权值都增加一个常量，使之对每条边的权值都增加一个常量，使之消除负边，然后再使用消除负边，然后再使用DijkstraDijkstra算法。算法。问题：经过边数多的路径，权值增加得问题：经过边数多的路径，权值增加得也多，并不等价于原问题也多，并不等价于原问题31一个可行的解决方案一个可行的解决方案 将加权图和非加权图算法组合起来将加权图和非加权图算法组合起来 思想：放弃思想：放弃knownknown的概念，穷举所有的路径，的概念，穷举所
25、有的路径，选择最短的一条。选择最短的一条。实现：利用一个队列实现：利用一个队列开始时，将源点开始时，将源点s s放入队列放入队列重复以下过程，直到队列为空：重复以下过程，直到队列为空：出队一个节点出队一个节点v v 对对v v的所有邻接点的所有邻接点w w，如果经过，如果经过v v到到w w的距离比已知的的距离比已知的s s到到w w的距离短，则更新的距离短，则更新w w的距离，并将的距离，并将w w入队入队32算法分析算法分析 适用于无负环的图适用于无负环的图 时间效益：每个节点至多出队时间效益：每个节点至多出队v v次，运行次，运行时间是时间是O(|E|O(|E|V|)|V|)33单源最短
26、路径单源最短路径非加权图的最短路径非加权图的最短路径 加权图的最短路径加权图的最短路径 带有负权值的图带有负权值的图无环图无环图给出一个加权图和图上的一个节点给出一个加权图和图上的一个节点s s，找出，找出s s到图中到图中每一节点的最短路径每一节点的最短路径34无环图的最短路径无环图的最短路径 当图中无环时，可以对当图中无环时，可以对DijkstraDijkstra算法进算法进行改进，使之达到行改进，使之达到O(|V|+|E|)O(|V|+|E|)的时间效的时间效益益 思想：按照拓扑排序的次序选择结点思想：按照拓扑排序的次序选择结点35V2V0V5V1V3V4V642133102416拓扑排
27、序：拓扑排序：2，0，5，1，3，4，6dpdpdpdpdp20042532160350416 1645dp7336第第14章章 最短路径问题最短路径问题 单源最短路径单源最短路径 所有顶点对间的最短路径所有顶点对间的最短路径37所有节点对的最短路径问题所有节点对的最短路径问题 方法一，对每一结点运行方法一，对每一结点运行DijkstraDijkstra最短路径算最短路径算法；法；方法二，用方法二，用FloydFloyd算法。时间复杂性算法。时间复杂性O(NO(N3 3)。具。具体思想是一次将每个节点作为中间节点，看看体思想是一次将每个节点作为中间节点，看看从起始点到中间结点，再从中间节点到终
28、止点从起始点到中间结点，再从中间节点到终止点的距离是不是比已知的距离短。如是，则替代。的距离是不是比已知的距离短。如是，则替代。38Floyd 算法算法 使用使用n n行行n n列的矩阵列的矩阵A A用于计算最短路径。用于计算最短路径。初始时，初始时，A i,j =c i,j A i,j =c i,j 进行进行n n次迭代次迭代 在进行第在进行第 k k 次迭代时，我们将使用如下的公式次迭代时，我们将使用如下的公式 A Ak-1k-1i,ji,j A Ak ki,j=MINi,j=MIN A Ak-1k-1i,k +Ai,k +Ak-1k-1k,j k,j 注意：第注意：第k k次迭代时，针对
29、结点次迭代时，针对结点k k进行。原进行。原A Ak-1k-1 矩阵的矩阵的第第k k行，第行，第k k列保持不变。左上至右下的对角线元素也列保持不变。左上至右下的对角线元素也不变。不变。39V1V2V05 53 38 82 20 8 53 0 2 00 1 20120 8 53 0 2 00 8 53 0 8 2 00 7 53 0 8 5 2 00 8 53 0 8 5 2 0A0A2A1A初值初值40存储设计存储设计 FloydFloyd算法除了给出任意两个结点之间的最算法除了给出任意两个结点之间的最短路径之外，还需要给出路径的组成。短路径之外，还需要给出路径的组成。每条路径信息也只保存
30、这条路径上的前一每条路径信息也只保存这条路径上的前一结点的信息。结点的信息。路径信息的保存需要一个路径信息的保存需要一个|V|V|V|V|的二维的二维数组数组prevprev。previjprevij的值表示从的值表示从i i到到j j的的最短路径上的前一结点的序号。最短路径上的前一结点的序号。41邻接矩阵类中邻接矩阵类中 Floyd算法的实现算法的实现 template void adjMatrixGraph:floyd()const TypeOfEdge*d=new TypeOfEdge*Vers;int*prev=new int*Vers;int i,j,k;/初始化初始化 for(i=
31、0;i Vers;+i)di=new TypeOfEdgeVers;previ=new intVers;for(j=0;j Vers;+j)dij=edgeij;previj=(edgeij!=noEdge)?i:-1;42/迭代过程迭代过程 for(k=0;k Vers;+k)for(i=0;i Vers;+i)for(j=0;j Vers;+j)if(dik+dkj dij)dij=dik+dkj;previj=prevkj;/输出过程输出过程 cout 最短路径长度：最短路径长度：endl;for(i=0;i Vers;+i)cout endl;for(j=0;j Vers;+j)cou
32、t dij t;cout 最短路径：最短路径：endl;for(i=0;i Vers;+i)cout endl;for(j=0;j Vers;+j)cout previj t;43总结总结 求结点之间的最短路径有很重要的应用。求结点之间的最短路径有很重要的应用。介绍了求单源最短路径和所有结点对之间介绍了求单源最短路径和所有结点对之间的最短路径的方法。的最短路径的方法。重点介绍了两个常用的算法：求单源最短重点介绍了两个常用的算法：求单源最短路径的路径的DijkstraDijkstra算法和求所有结点之间的算法和求所有结点之间的最短路径的最短路径的FloydFloyd算法。算法。44作业作业 P396 1，2，15，17，26
