数据结构：思想与方法-第十四章课件

1、1第14章 最短路径问题 单源最短路径所有顶点对间的最短路径1第14章 最短路径问题 单源最短路径2单源最短路径非加权图的最短路径 加权图的最短路径 带有负权值的图无环图给出一个加权图和图上的一个节点s，找出s到图中每一节点的最短路径2单源最短路径非加权图的最短路径 给出一个加权图和图上的一个3非加权的最短路径采用广度优先搜索，它按层处理一层的所有结点：离起始结点最近的结点最先处理，距离最远的最晚处理。具体过程：从s到s的最短路径为0通过搜索S的所有邻接结点就能找到离S距离为1的所有结点搜索离S距离为1的所有结点的邻接结点就能找到距离为2的节点重复上述过程，直到所有节点都访问到为止3非加权的最

2、短路径采用广度优先搜索，它按层处理一层的所有结点4找v2到其他节点的最短距离V2V0V5V1V3V4V60V2V0V5V1V3V4V6011V2V0V5V1V3V4V601122V2V0V5V1V3V4V601122334找v2到其他节点的最短距离V2V0V5V1V3V4V60V5存储设计数组distance：记录从源点到达每个结点的最短距离。数组prev：记录要到达此结点，必须到达的前一结点。例如，对于上图中的结点v4，prevv4记录的是v1。也就是说，从源点到达v4必须先到v1。而prevv1记录的是v0，prevv0记录的是v2。从prev数组，我们可以追溯到这条路径。例如，对于v4，

3、我们可以追溯到这条路径为v2-v0-v1-v4。 5存储设计数组distance：记录从源点到达每个结点的最短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= cu

4、rDistanve+1； prevv = u； .6过程抽象unweightedShortDistance(s7分析算法的时间复杂度为O（|V|E|）。算法效率之所以低的原因之一在于：为保证所有结点都找到了最短路径，算法假设最长的路径是经过所有的结点。该算法效率之所以低的第二个原因在于：内层循环的设计。在处理距离为d的结点时，我们找到了所有距离为d+1的结点。但算法并没有利用这个成果，而在下一个循环周期中又用顺序查找的方法检查了所有结点，从中挑出距离为d+1的结点。这浪费了大量的时间。7分析算法的时间复杂度为O（|V|E|）。8算法的改进外层循环没必要执行|V|次，只要所有的结点都已找到了最短

5、距离就可以了。第二层循环也没必要执行|V|次，只要检查新找到最短路径的结点。用一个队列保存新找到路径的结点8算法的改进外层循环没必要执行|V|次，只要所有的结点都已找9改进算法的伪代码unweightedShortDistance(start) for （每个结点v） distance(v) = 无穷大； distancestart = 0; start入队; while （队列非空） 取出队头元素存入u； for (u的每一个邻接点v) if（distancev= 无穷大） distancev= distanceu + 1； prevv = u； v入队； . 9改进算法的伪代码unweig

6、htedShortDistan10邻接表中的实现template void adjListGraph :unweightedShortDistance (TypeOfVer start, TypeOfEdge noEdge) 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; 10邻接表中的实现template class Ty

7、peO11/寻找起始结点的编号 for (sNo = 0; sNo Vers; + sNo) if (verListsNo.ver = start) break; if (sNo = Vers) cout 起始结点不存在 next) if (distancep-end = noEdge) distancep-end = distanceu + 1; prevp-end = u; q.enQueue(p-end); /输出最短路径 for (i = 0; i Vers; +i) cout 从 start 到 verListi.ver 的路径为: endl; printPath(sNo, i, p

8、rev); cout endl; 11/寻找起始结点的编号12队列的变化： d2=00 5 d0=1, d5=11 3 d1=2, d3 = 234 d4=36 d6 = 36空 算法结束V2V0V5V1V3V4V612队列的变化：V2V0V5V1V3V4V613printPath函数的实现 路径的存储不是正向的。即可以从第一个结点找到第二个结点，从第二个结点找到第三个结点，。而是逆向存储的，即最后一个结点记住倒数第二个结点，倒数第二个结点记住倒数第三个结点，。适合用递归处理。于是我们定义了一个私有的递归成员函数printPath来输出这条路径。 13printPath函数的实现 路径的存储不

9、是正向的。即可14template void adjListGraph :printPath(int start, int end, int prev) const if (start = end) cout verListstart.ver ;return; printPath(start, prevend, prev); cout - verListend.ver ; 14template class TypeOfVer, c15函数的输出从v2到v0的路径为：v2 v0从v2到v1的路径为：v2 v0 - v1从v2到v2的路径为：v2从v2到v3的路径为：v2 v0 v3从v2到v4的

10、路径为：v2 v0 v3 v4从v2到v5的路径为：v2 v5从v2到v6的路径为：v2 v0 v3 v6 V2V0V5V1V3V4V615函数的输出从v2到v0的路径为：V2V0V5V1V3V416时间复杂度算法的主体是while循环，该循环一直执行到队列为空。而图中的每个结点都必须而且仅入队一次，因此该循环必须执行|V|个循环周期。每个循环周期检查出队结点的所有边，整个while循环检查了图中所有的边。因此，while循环的运行时间为O（|E|）。前面的一些辅助工作，如初始化、寻找起始结点的编号等所需要的时间是O（|V|）。所以算法的总运行时间为O（|V|+|E|）。 16时间复杂度算法的

11、主体是while循环，该循环一直执行到队17单源最短路径非加权图的最短路径 加权图的最短路径 带有负权值的图无环图给出一个加权图和图上的一个节点s，找出s到图中每一节点的最短路径17单源最短路径非加权图的最短路径 给出一个加权图和图上的一18Dijkstra算法保存了一个顶点集S。S中的顶点是已经找到了最短路径的顶点。开始时，顶点集合S只包含源点一个顶点。反复执行以下循环，直至顶点集S 包含所有的顶点为止：对于在顶点集V - S中的每个顶点，考察新加入顶点集S中的结点是否有边到达自己。如果存在，则检查这条路径是否比原来已知的路径要短。如果是，则更新源点到此结点的距离和路径；然后，从V S中寻找

12、一个路径最短的结点，从源点到这个结点已经不可能有更好的路径了，把它加入顶点集S18Dijkstra算法保存了一个顶点集S。S中的顶点是已经194V2V0V5V1V3V4V6421253102481654V2V0V5V1V3V4V642125310248165654V2V0V5V1V3V4V642125310248165654V2V0V5V1V3V4V6421253102481656579194V2V0V5V1V3V4V64212531024816204V2V0V5V1V3V4V64212531024816565794V2V0V5V1V3V4V64212531024816565794V2V0V5

13、V1V3V4V6421253102481656579204V2V0V5V1V3V4V6421253102481621存储设计和非加权图的实现中一样，需要保存的距离和路径信息还需要保存哪些结点在S中，哪些结点不在S中的信息。设计三个数组：distance、prev和known， 21存储设计和非加权图的实现中一样，需要保存的距离和路径信息22伪代码void dijkstra( start ) for （图中的每个顶点v） distancev = INFINITY; knownv = false; distancestart = 0; for (i = 1; i Vers; +i) v = 所有k

14、nown标记为false的结点中的路径最短者； knownv = true; for （v的每一个邻接点w） if (knownw 等于false & distancev + (v,w)的权值 distancew ) distancew = distancev + (v,w)的权值 Prevw = v; 22伪代码void dijkstra( start )23邻接表类中实现的Dijkstra算法 template void adjListGraph :dijkstra(TypeOfVer start, TypeOfEdge noEdge) const TypeOfEdge *distance

15、 = new TypeOfEdgeVers; int *prev = new int Vers; bool *known = new boolVers; int u, sNo, i, j; edgeNode *p; TypeOfEdge min; for (i = 0; i Vers; +i) /初始化 knowni = false; distancei = noEdge; 23邻接表类中实现的Dijkstra算法 template 24for (sNo = 0; sNo Vers; +sNo) if (verListsNo.ver = start) break; if (sNo = Vers

16、) 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-end min + p-weight) distancep-end = min + p-weight; prevp-end = u; for (i = 0; i Vers; +i) /输出所有的路径信息 cout 从 start 到 ve

17、rListi.ver 的路径为: endl; printPath(sNo, i, prev); cout t长度为： distancei endl; 24for (sNo = 0; sNo Vers; +25执行dijkstra函数的过程 ：源点为v1udist 0prev0known0dist 1prev1known1dist 2prev2known2dist3prev3known3dist 4prev4known4dist 5prev5known5dist 6prev6known6, -, F0, 1, F, -, F, -, F, -, F, -, F, -, F1, -, F0, 1,

18、 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, TV2V0V5V1V3V4V

19、6421253102481625执行dijkstra函数的过程 ：源点为v1udist 26输出结果从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 长度为：726输出结果从v1到v0的路径为：27时间复杂度Dijkstra 算法运行时间主要由两部分组成：查找路径最短的尚未在S中的结点u，以及扫描u的邻接点

20、，更新他们的距离。每次找出距离最短的结点所需的时间是O(|V|)，在整个算法的执行过程中，寻找距离最短的结点将花去O(|V|2)的时间。更新V - S中的结点的距离所需的时间是O(|E|)总的时间复杂度是O(|E|+|V|2) = O(|V|2) 27时间复杂度Dijkstra 算法运行时间主要由两部分组成28单源最短路径非加权图的最短路径 加权图的最短路径 带有负权值的图无环图给出一个加权图和图上的一个节点s，找出s到图中每一节点的最短路径28单源最短路径非加权图的最短路径 给出一个加权图和图上的一29带有负权值的图如果一个图带有负权值的边，Dijkstra算法无法正常工作V2V0V5V1V

21、3V4V64212331024-816如按Dijkstra算法，从结点2出发首先会认为结点5是已知节点，但事实上，2-0-3-5是一条更短的路径。29带有负权值的图如果一个图带有负权值的边，Dijkstra30一个直观的解决方案对每条边的权值都增加一个常量，使之消除负边，然后再使用Dijkstra算法。问题：经过边数多的路径，权值增加得也多，并不等价于原问题30一个直观的解决方案对每条边的权值都增加一个常量，使之消除31一个可行的解决方案将加权图和非加权图算法组合起来思想：放弃known的概念，穷举所有的路径，选择最短的一条。实现：利用一个队列开始时，将源点s放入队列重复以下过程，直到队列为空

22、：出队一个节点v对v的所有邻接点w，如果经过v到w的距离比已知的s到w的距离短，则更新w的距离，并将w入队31一个可行的解决方案将加权图和非加权图算法组合起来32算法分析适用于无负环的图时间效益：每个节点至多出队v次，运行时间是O(|E | |V|)32算法分析适用于无负环的图33单源最短路径非加权图的最短路径 加权图的最短路径 带有负权值的图无环图给出一个加权图和图上的一个节点s，找出s到图中每一节点的最短路径33单源最短路径非加权图的最短路径 给出一个加权图和图上的一34无环图的最短路径当图中无环时，可以对Dijkstra算法进行改进，使之达到O(|V|+|E|)的时间效益思想：按照拓扑排

23、序的次序选择结点34无环图的最短路径当图中无环时，可以对Dijkstra算法35V2V0V5V1V3V4V642133102416拓扑排序：2，0，5，1，3，4，6dpdpdpdpdp200425321603504161645dp7335V2V0V5V1V3V4V642133102416拓扑排36第14章 最短路径问题 单源最短路径所有顶点对间的最短路径36第14章 最短路径问题 单源最短路径37所有节点对的最短路径问题方法一，对每一结点运行Dijkstra最短路径算法；方法二，用Floyd算法。时间复杂性O(N3)。具体思想是一次将每个节点作为中间节点，看看从起始点到中间结点，再从中间节点

24、到终止点的距离是不是比已知的距离短。如是，则替代。37所有节点对的最短路径问题方法一，对每一结点运行Dijks38Floyd 算法使用n行n列的矩阵A用于计算最短路径。 初始时， A i, j = c i, j 进行n次迭代 在进行第 k 次迭代时，我们将使用如下的公式 Ak-1i,j Aki,j = MIN Ak-1i,k + Ak-1k,j 注意：第k次迭代时，针对结点k进行。原Ak-1 矩阵的第k行，第k列保持不变。左上至右下的对角线元素也不变。 38Floyd 算法使用n行n列的矩阵A用于计算最短路径。39V1V2V053820 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初值39V1V2V053820 8 50 40存储设计Floyd算法除了给出任意两个结点之间的最短路径之外，还需要给出路径的组成。每条路径信息也只保存这条路径上的前一结点的信息。路径信息的保存需要一个|V|V|的二维数组prev。previj的值表示从i到j的最短路径上的前一结点的序号。40存储设计Floyd算法除了给出任意