DS07-图05-最短路径.ppt

1、第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,7.6 最短路径,所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。,A到E的路径有： AE：100 ADE：90 ADCE：60 ABCE：70,1.单源点最短路径 2.所有顶点对之间的最短路径,问题描述：给定带权有向图G(V, E)和源点vV，求从v到G中其余各顶点的最短路径。,单源点最短路径问题,应用实例计算机网络传输的问题：怎样找到一种最经

2、济的方式，从一台计算机向网上所有其它计算机发送一条消息。,迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。,基本思想：设置一个集合S 存放已经找到最短路径的顶点，S 的初始状态只包含源点v，对vi V-S，假设从源点v到vi 的有向边为最短路径。以后每求得一条最短路径v, , vk，就将vk 加入集合S中，并将路径v, , vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V 中全部顶点加入到集合S 中。,Dijkstra算法,Dijkstra算法的基本思想,假设 S为已求得最短路径的终点的集合，则可证明：下

3、一条最短路径(设其终点为x)或者是弧(v，x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明。假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的路径。但是，这是不可能的。因为我们是按路径长度递增的次序来产生各最短路径的，即长度比此路径短的所有路径均己产生，它们的终点必定在S中，即假设不成立。,10,50,30,10,100,20,60,S=A AB:(A, B)10 AC:(A, C) AD: (A, D)30 AE: (A, E)100,10,50,30,10,100,20,60,S=A, B AB:(A, B)10 AC:(A, B, C)6

4、0 AD: (A, D)30 AE: (A, E)100,10,50,30,10,100,20,60,S=A, B AB:(A, B)10 AC:(A, B, C)60 AD: (A, D)30 AE: (A, E)100,10,50,30,10,100,20,60,S=A, B, D AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, E)90,10,50,30,10,100,20,60,S=A, B, D AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, E)90,10,50,30,10,

5、100,20,60,S=A, B, D, C AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, C, E)60,10,50,30,10,100,20,60,S=A, B, D, C, E AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, C, E)60,例：给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。,V5,V0,V2,V4,V1,V3,100,300,10,60,10,20,50,5,V0,V2,V4,V3,V5,V0,始点 终点 Di 最短路径,V1 V2 V3 V4

6、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), 1

7、0 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),辅助结构,int D Dv:表示当前从源v0到顶点v的最短路径长度 int P Pvw为TRUE，则w是从v0到v当前求得最短路径上的顶点 Pv:表示从源v0到顶点v的最短路径上顶点v的所有前驱顶点 int final finalv为TRUE当且

8、仅当vS，即已经求得v0到v的最短路径,Dijkstra算法,(1) 假设我们以带权的邻接矩阵arcs表示有向网。 S：已求得最短路径的终点的集合。初始为空。 D初始化 Dvi=arcsv0vi vi V (2) 选择vj，使得Dj=MinDi|vi V-S 令S=Svj (3) 修改从v出发到集合V-S上任意顶点vk可达的最短路径长度。 若 Dj+arcsjk Dk, 则Dk=Dj+arcsjk (4) 重复(2),(3)共n-1次。 由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。,V0 V1 V2 V3 V4 V5 V0 10 30 100 V1 5 V2 50 V3 10

9、 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次。这样，便可求得每一对顶点之间的最短路径。总的执

10、行时间为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。,弗洛伊德算法思想 欲求Vi到Vj的最短路径，依次求得中间顶点序号不大于k（k=0,1,.n-1）的最短路径。 具体过程P190.,定义一个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的 最短路径的长度;

11、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.熟悉图的各种存储结构及构造算法(特别是邻接矩阵和邻接表)，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 2.熟练掌握图的两种搜索路径的遍历及算法。 3.掌握以下内容： 图的最小生成树和求最小生成树算法的思想; AOV网络的拓扑排序问题； AOE网络的关键路