最短路径与图的小结.ppt

,数 据 结 构 主讲：信息工程大学电子技术学院 402教研室,第21讲,第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,7.6 最短路径,所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。 1.单源点最短路径 2.所有顶点对之间的最短路径,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,始点 终点 Di 最短路径,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以外的顶点，其相应的数组元素Si 为 0 ，否则为 1 。,另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为Di=costV0i，i=1n。数组D中的数据随着算法的逐步进行要不断地修改 定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使Dw的值最小。于是从源点到达w只通过S中的顶点，把 w 加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离： 取Dv和Dw+costwv中值较小的作为新的Dv 重复上述，直到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,V1,i=5,i=4,i=3,i=2,i=1,D 终点,7.6 最短路径,7.6.1 单源点最短路径 7.6.2 所有顶点对之间的最短路径,问题描述： 已知一个各边权值均大于 0 的带权有向图，对每对顶点 vivj，要求求出每一对顶点之间的最短路径和最短路径长度。 解决方案： 1. 每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。,弗洛伊德算法思想： 假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为arcsij的路径，该路径不一定是最短路径，尚需进行n次试探。 首先考虑路径（Vi,V0,Vj）是否存在（即判别（Vi,V0）、（V0,Vj）是否存在）。如存在，则比较（Vi,Vj）和（Vi,V0,Vj）的路径长度，取长度较短者为从 Vi到Vj 的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点 V1，依次类推。可同时求得各对顶点间的最短路径。,定义一个n阶方阵序列 D(-1),D(0),D(1),D(2),D(k),D(n-1) 其中： D(-1)ij= arcsij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 0kn-1 可见，D(1)ij就是从vi到vj的中间顶点的序号不大于1的 最短路径的长度; D(k)ij就是从vi到vj的中间顶点的序号不大于k的 最短路径的长度; D(n-1)ij就是从vi到vj的最短路径的长度。,各顶点间的最短路径及其路径长度,最短路径弗洛伊德举例,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,P(2),P(1),P(0),P(-1),P,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,D(2),D(1),D(0),D(-1),D,本章小结 1.熟练图的各种存储结构及构造算法，了解实际问题的