4 最短路径.pdf

《4 最短路径.pdf》由会员分享，可在线阅读，更多相关《4 最短路径.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4 4讲：讲：最短路径最短路径 所谓最短路径问题是指：如果从图中某一顶点（称所谓最短路径问题是指：如果从图中某一顶点（称 为源点）出发到达另一顶点（称为终点）的路径可能不为源点）出发到达另一顶点（称为终点）的路径可能不 止一条，如何找到一条路径使得沿此路径上各边的权值止一条，如何找到一条路径使得沿此路径上各边的权值 总和达到最小。总和达到最小。 1.1.单源点最短路径单源点最短路径 2.2.所有顶点对之间的最短路径所有顶点对之间的最短路径 给定带权有向图给定带权有向图G G和源点和源点v v, , 求从求从v v到到G G中其余各顶点中其余各顶点 的最短路径。的最短路径。 V5 V0 V2

2、 V4 V1V3 100 30 10 60 10 20 505 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

3、) (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) 第第4讲：讲：最短路径最短路径 第第4 4讲：最短路径讲：最短路径 如何在计算机中求如何在计算机

4、中求 得最短路径？得最短路径？ 第第4 4讲：最短路径讲：最短路径 DijkstraDijkstra提出了一个按路径提出了一个按路径“长度长度”递增的次序，逐递增的次序，逐 步得到由给定源点到图的其余各点间的最短路径的算法：步得到由给定源点到图的其余各点间的最短路径的算法： n假设我们以邻接矩阵假设我们以邻接矩阵costcost表示所研究的有向网。表示所研究的有向网。 n迪杰斯特拉算法需要一个顶点集合，初始时集合内只迪杰斯特拉算法需要一个顶点集合，初始时集合内只 有一个源点有一个源点V V0 0 ，以后陆续将已求得最短路径的顶点，以后陆续将已求得最短路径的顶点 加入到集合中，到全部顶点都进入集

5、合了，过程就结加入到集合中，到全部顶点都进入集合了，过程就结 束了。集合可用一维数组来表示，设此数组为束了。集合可用一维数组来表示，设此数组为S S，凡，凡 在集合在集合S S以外的顶点，其相应的数组元素以外的顶点，其相应的数组元素SiSi为为0 0，否，否 则为则为 1 1 。 n另需一个一维数组另需一个一维数组D D，每个顶点对应数组的一个单元，每个顶点对应数组的一个单元， 记录从源点到其他各顶点当前的最短路径长度，其初值记录从源点到其他各顶点当前的最短路径长度，其初值 为为DiDi=costV=costV0 0ii，i=1i=1n n。数组。数组D D中的数据随着算法中的数据随着算法 的

6、逐步进行要不断地修改的逐步进行要不断地修改 n定义了定义了S S集合和集合和D D数组并对其初始化后，迪杰斯特拉算法数组并对其初始化后，迪杰斯特拉算法 在进行中，都是从在进行中，都是从S S之外的顶点集合中选出一个顶点之外的顶点集合中选出一个顶点w w， 使使DwDw 的值最小。于是从源点到达的值最小。于是从源点到达w w只通过只通过S S中的顶点，中的顶点， 把把 w w 加入集合加入集合S S中，并调整中，并调整D D中记录的从源点到集合中中记录的从源点到集合中 每个顶点每个顶点v v的距离：的距离： 取取DvDv 和和Dw+costwvDw+costwv 中值较小的作为新的中值较小的作为

7、新的DvDv n重复上述，直到重复上述，直到S S中包含中包含V V中其余各顶点的最短路径。中其余各顶点的最短路径。 第第4 4讲：最短路径讲：最短路径 第4讲：最短路径 V0 V1 V2 V3 V4 V5 V0 10 30 100 V1 5 V2 50 V3 10 V4 20 60 V5 V0 V2 V1 V4 V5 V3 550 30 10 10 100 60 20 V0 0,V2 2,V4 4,V3 3,V5 5 ,V1 1V0 0,V2 2,V4 4,V3 3,V5 5V0 0,V2 2,V4 4,V3 3V0 0,V2 2,V4 4V0 0,V2 2S=V0 0 V1 1V5 5V3

8、 3V4 4V2 2Vj j V5 5 V4 4 V3 3 V2 2 60 30 50 10 60V0,4,3,5 30 50 10 90V0,4,5 30 50V0,4,3 10 100V0,5 30V0,4 60V0,2,3 10 100V0,5 30V0,4 10V0,2 V1 1 i=5i=4i=3i=2i=1 D 终点终点 第第4 4讲：最短路径讲：最短路径 问题描述：问题描述： 已知一个各边权值均大于已知一个各边权值均大于 0 0 的带权有向图，对每对的带权有向图，对每对 顶点顶点 vivjvivj，要求求出每一对顶点之间的最短路径和最，要求求出每一对顶点之间的最短路径和最 短路径

9、长度。短路径长度。 解决方案：解决方案： 1. 1. 每次以一个顶点为源点，重复执行迪杰斯特拉算每次以一个顶点为源点，重复执行迪杰斯特拉算 法法n n次。这样，便可求得每一对顶点之间的最短路径。总次。这样，便可求得每一对顶点之间的最短路径。总 的执行时间为的执行时间为O(nO(n3 3) )。 2. 2. 形式更直接的弗洛伊德（形式更直接的弗洛伊德（FloydFloyd）算法。时间复杂）算法。时间复杂 度也为度也为O(nO(n3 3) )。 2 2、所有顶点对之间的最短路径、所有顶点对之间的最短路径 第第4 4讲：最短路径讲：最短路径 弗洛伊德算法思想：弗洛伊德算法思想： 假设求从顶点假设求从

10、顶点V Vi i到到V Vj j的最短路径。如果从的最短路径。如果从V Vi i到到V Vj j有弧，有弧， 则从则从V Vi i到到V Vj j存在一条长度为存在一条长度为arcsijarcsij的路径，该路径不的路径，该路径不 一定是最短路径，尚需进行一定是最短路径，尚需进行n n次试探。次试探。 首先考虑路径（首先考虑路径（V Vi i,V,V0 0,V,Vj j）是否存在（即判别（）是否存在（即判别（V Vi i,V,V0 0 ）、（）、（V V0 0,V,Vj j）是否存在）。如存在，则比较（）是否存在）。如存在，则比较（V Vi i,V,Vj j）和（）和（ V Vi i,V,V0

11、 0,V,Vj j）的路径长度，取长度较短者为从）的路径长度，取长度较短者为从 V Vi i到到V Vj j 的中间的中间 顶点的序号不大于顶点的序号不大于0 0 的最短路径。假如在路径上再增加一的最短路径。假如在路径上再增加一 个顶点个顶点 V V1 1，依次类推。可同时求得各对顶点间的最短路依次类推。可同时求得各对顶点间的最短路 径。径。 第第4 4讲：最短路径讲：最短路径 定义一个定义一个n n阶方阵序列阶方阵序列 D D(-1) (-1),D ,D(0) (0),D ,D(1) (1),D ,D(2) (2), ,D ,D(k) (k), ,D ,D(n-1) (n-1) 其中：其中：

12、 D D(-1) (-1)ij= arcsij ij= arcsij D D(k) (k)ij=Min D ij=Min D(k-1) (k-1)ij, D ij, D(k-1) (k-1)ik+ D ik+ D(k-1) (k-1)kj kj 0kn-1 0kn-1 可见，可见，D D(1) (1)ij ij就是从就是从v vi i到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于1 1的的 最短路径的长度最短路径的长度; ; D D(k) (k)ij ij就是从就是从v vi i到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于k k的的 最短路径的长度最短路径的长度;

13、 ; D D(n-1) (n-1)ij ij就是从就是从v vi i到到v vj j的最短路径的长度。的最短路径的长度。 0 4 11 6 0 2 3 0 第第4 4讲：最短路径讲：最短路径 2 1 CABCA BCBCA ABCAB CABCA BCBA ABCAB CABCA BCBA ACAB0 210210210210 P(2)P(1)P(0)P(-1) P 2 1 073 205 640 073 206 640 073 206 1140 0 3 206 1140 0 210210210210 D(2)D(1)D(0)D(-1) D CA BCBA ACAB 0 4 11 6 0 2 3 0 第第4 4讲：最短路径讲：最短路径