第21讲 最短路径与图的小结5.pptVIP

7.6 最短路径 所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。 1.单源点最短路径 2.所有顶点对之间的最短路径 7.6 最短路径 7.6.1 单源点最短路径 7.6.2 所有顶点对之间的最短路径 问题描述：???? 已知一个各边权值均大于 0 的带权有向图，对每对顶点 vi≠vj，要求求出每一对顶点之间的最短路径和最短路径长度。 解决方案： 1. 每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。 数 据 结 构 主讲：信息工程大学电子技术学院 402教研室 第21讲 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.6.1 单源点最短路径 给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。 V5 V0 V2 V4 V1 V3 100 30 10 60 10 20 50 5 V0 V2 V4 V3 V5 V0 始点 终点 D[i] 最短路径 V1 V2 V3 V4 V5 ∞ 10 ∞ 30 100 ∞ 10 ∞ 30 100 ∞ 10 60 30 100 ∞ 10 60 30 100 ∞ 10 50 30 100 (V0, V2) (V0, V4) (V0, V5) (V0, V2) (V0, V4) (V0, V5) (V0, V2) (V0, V2, V3) (V0, V4) (V0, V5) (V0, V2) (V0, V2, V3) (V0, V4) (V0, V5) (V0, V2) (V0, V4, V3) (V0, V4) (V0, V5) ∞ 10 50 30 90 (V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V5) ∞ 10 50 30 90 (V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V5) ∞ 10 50 30 60 (V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V3, V5) ∞ 10 50 30 60 (V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V3, V5) 如何在计算机中求得最短路径？ Dijkstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法： 假设我们以邻接矩阵cost表示所研究的有向网。 迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0 ，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素S[i] 为 0 ，否则为 1 。 另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为D[i]=cost[V0][i]，i=1…n。数组D中的数据随着算法的逐步进行要不断地修改 定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使D[w]的值最小。于是从源点到达w只通过S中的顶点，把 w 加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离： 取D[v]和D[w]+cost[w][v]中值较小的作为新的D[v] 重复上述，直到S中包含V中其余各顶点的最短路径。 V0 V1 V2 V3 V4 V5 V0 ∞ ∞ 10 ∞ 30 100 V1 ∞ ∞ 5 ∞ ∞ ∞ V2 ∞ ∞ ∞ 50 ∞ ∞ V3 ∞ ∞ ∞ ∞ ∞ 10 V4 ∞ ∞ ∞ 20 ∞ 60 V5 ∞ ∞ ∞ ∞ ∞ ∞ {V0,V2,V4,V3,V5 ,V1} {V0,V2,V4,V3,V5} {V0,V2,V4,V3} {V0,V2,V4} {V0,V2} S={V0} V1 V5 V3 V4 V2 Vj V5 V4 V3 V2 60 30 50 10 ∞ 60{V0,4,3,5} 30 50 10 ∞ 90{V0,4,5} 30 50{V0,4,3} 10 ∞ 100{V0,5} 30{V0,4}