最短路问题DijkstraFloyd算法

1、 最短路问题最短路问题 赵嘉诚赵嘉诚Dijkstra算法算法Ford算法算法Floyd算法算法SPFA算法算法一、什么是最短路问题一、什么是最短路问题例例 下图为单行线交通网，每弧旁的数字表示通过这条下图为单行线交通网，每弧旁的数字表示通过这条 线所需的费用。现在某人要从线所需的费用。现在某人要从v1出发，通过这个交出发，通过这个交 通网到通网到v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从从v1到到v8：P1=（v1，v2，v5，v8） 费用费用 6+1+6=13P2=（v1，v3，v4， v6， v

2、7， v8） 费用费用 3+2+10+2+4=21P3= 旅行路线总费用旅行路线总费用 路上所有弧权之和。路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。最短路问题中，不考虑有向环、并行弧。即即适用于适用于DAG（有向无环图）（有向无环图）v2v523464v3v1v4v6121061210v8v9v72363最短路问题严格的定义最短路问题严格的定义 给定有向网络给定有向网络D=（V(点点)，A（弧），（弧），W（权），任意弧（权），任意弧aijA，有权，有权w（ aij ）=wij，给定，给定D中的两个顶点中的两个顶点A，B。设。设P是是D中从中从A到到B的一条路，的一条路，定义路定义

3、路P的权（长度）是的权（长度）是P中所有弧的权之和，记为中所有弧的权之和，记为w（P）。最短路问题就是要在所有从）。最短路问题就是要在所有从vs到到vt的路中，求的路中，求一条路一条路P0 ，使，使(P)min)(PP0ww 称称P0是从是从vs到到vt的最短路。路的最短路。路P0的权称为从的权称为从vs到到vt的路长。记为的路长。记为ust。 最短路径问题是图论研究中的一个经典算法问最短路径问题是图论研究中的一个经典算法问题，题， 旨在寻找图（由结点和路径组成的）中两旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。结点之间的最短路径。 算法具体的形式包括：算法具体的形式包括： 确定起

4、点的最短路径问题确定起点的最短路径问题 - 即已知起始结点，即已知起始结点，求最短路径的问题。求最短路径的问题。 确定终点的最短路径问题确定终点的最短路径问题 - 与确定起点的问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。方向反转的确定起点的问题。 确定起点终点的最短路径问题确定起点终点的最短路径问题 - 即已知起点和即已知起点和终点，求两结点之间的最短路径

5、。终点，求两结点之间的最短路径。 全局最短路径问题全局最短路径问题 - 求图中所有的最短路径求图中所有的最短路径。二、二、Dijkstra（迪杰特斯拉）算法（迪杰特斯拉）算法 当所有当所有 wij 0 时，时，本算法是用来本算法是用来求给定点求给定点vs到到任一个点任一个点vj 最短路最短路的公认的最好方法。的公认的最好方法。事实：如果事实：如果P是是D中从中从vs到到vj的最短路，的最短路，vi是是P中的一中的一个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到 vi的最短路。的最短路。 最短路的子路也是最短路。最短路的子路也是最短路。DijkstraDijkstra算法

6、是典型的最短路径路由算法，用于算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展特点是以起始点为中心向外层层扩展，直到扩展到终点为止。到终点为止。DijkstraDijkstra算法能得出最短路径的最算法能得出最短路径的最优解，优解，但由于它遍历计算的节点很多，所以效率但由于它遍历计算的节点很多，所以效率低。低。 思想：将思想：将D=（V，A，W）中）中vs到所有其它顶点的最短到所有其它顶点的最短 路按其路按其路长路长从小到大排列为：从小到大排列为：u0 u1 u2 unu0表示表示v

7、s到自身的长度，相应最短路记为：到自身的长度，相应最短路记为：P0，P1，P2，Pn， sivswuvi0X1000min , XVX ,X则记取最小值的点为取最小值的点为v1， P1=P（vs，v1） 假定假定 u0，u1，uk的值已求出，对应的最短路的值已求出，对应的最短路分别为分别为P1=P（vs，v1），）， P2=P（vs，v2），）， Pk=P（vs，vk）P1一定只有一条弧。一定只有一条弧。 记记 kkkskvvvvXVX , ,.,X21 则则 ) ,w(miniXX1vvuuivvkkki 使上式达到最小值的点使上式达到最小值的点v 可取为可取为vk+1。 计算过程中可采用标

8、号方法。计算过程中可采用标号方法。 Xk中的点，中的点，ui 值是值是vs 到到vi 的最短路长度，相应的的最短路长度，相应的点记点记“永久永久”标号；标号； XK中的点，中的点，ui值是值是vs到到vi的最短路长度的上界，的最短路长度的上界，相应的点记相应的点记“临时临时”标号，供进一步计算使用。标号，供进一步计算使用。前点标号前点标号 i : 表示点表示点vs到到vj的最短路上的最短路上vj的前一点。的前一点。如如 i=m，表示，表示vs到到vj的最短路上的最短路上vj前一点是前一点是vm。 6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v

9、60 1 36图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60 1 36v5v223464v3v1v41210 6 1210v8v9v72363v60 111 3图上标号法图上标号法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60 111 36图上标号法图上标号法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60 111 35图上标号法图上标号法:5v5v223464v3v1v41210 6 1210v8v9v72363v60 111 3图上标号法图上标号法:5v5v2

10、23464v3v1v41210 6 1210v8v9v72363v60 111 36图上标号法图上标号法:5v5v223464v3v1v41210 6 1210v8v9v72363v6011163图上标号法图上标号法:5v5v223464v3v1v41210 6 1210v8v9v72363v6010161239图上标号法图上标号法:5v5v223464v3v1v41210 6 1210v8v9v72363v6010161239图上标号法图上标号法:Dijkstra算法步骤：算法步骤：第第1步：令步：令us= 0，uj=wsj （1jn）若）若asj A，则，则第第2步：步：(选永久标号选永久

11、标号)在在XK中选一点中选一点vi，满足，满足 第第3步：（给点步：（给点vi永久性标号）永久性标号） 第第4步：步：(修改临时标号修改临时标号)对所有对所有 如果如果 , Xv 1kj jijiuwu 令令 j=i，uj=ui+wij否则否则, i,uj 不变不变,把把k换成换成k+1，返回第返回第2步。步。 jXviuminu Kj 如果如果ui=+ ，停止，停止，令令Xk+1= Xkvi,Xk+1= Xkvi令令wsj=+ , X0=vs ,X0=VX0 ,k=0, i=0 (0 jn）从从vs到到XK中各点没有路；否则，转第中各点没有路；否则，转第3步。步。如果如果Xk+1 = ，结束

12、，到所有的点的最短路已经求结束，到所有的点的最短路已经求得得 ；否则，转第；否则，转第4步。步。例例 用用Dijkstra算法求前面例子中从算法求前面例子中从v1到各点的最短路。到各点的最短路。解：解：u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+ ， j=1 （j=2，3，9）X0=v1 ，X0=v2，v3，v9v2v523464v3v1v4v6121061210v8v9v72363K=0 minu2，u3，u4，u5，u6，u7，u8，u9 =min6，3，1， ， ， ， ， =1= u4 点点v4得永久标号，得永久标号， 4=1 ，X1=v1，v4， X1=v

13、2，v3， v5，v6 ，v7，v8 ，v9，在所有在所有vjX1中，中， u6= ，u4+w46=1+10=11， 即即 u4+w46 u6 修改临时标号修改临时标号u6= 11 ， 6=4 ，其余标号不变。，其余标号不变。v2v523464v3v1v4v6121061210v8v9v72363K=0 +1=1 minu2，u3，u5，u6，u7，u8，u9 =min6，3， ， 11， ， ， =3= u3 点点v3得永久标号，得永久标号， 3=1 ，X2=v1，v4 ，v3， X2=v2， v5，v6 ，v7，v8 ，v9， u2= 6 ，u3+w32=3+2=5， 即即 u3+w32

14、u2 修改临时标号修改临时标号u2= 5 ， 2=3 ，其余标号不变。，其余标号不变。在所有在所有vjX2中中， k=2 +1=3 minu5，u6，u7，u8，u9 =min6，11， ， ， =6= u5 点点v5得永久标号，得永久标号， 5=2 ， X4=v1，v4 ，v3 ，v2， v5， X4=v6 ，v7，v8 ，v9， u6= 11 ，u5+w56=6+4=10， 即即 u5+w56 u6 u7= ，u5+w57=6+3=9， 即即 u5+w57 u7 u8= ，u5+w58=6+6=12， 即即 u5+w58 u8 修改临时标号修改临时标号u6= 10 ， 6=5 ， u7=9

15、 ， 7=5 ， u8= 12 ， 8=5 ，在所有在所有vjX4中，中， K=3 +1=4 minu6，u7，u8，u9 =min10，9，12， =9= u7 点点v7得永久标号，得永久标号， 7=5 ，X2=v1，v4 ，v3 ， v2， v5，v7，X2=v6 ，v8 ，v9，在在vjX5中，临时标号不变。中，临时标号不变。K=4 +1=5 minu6，u8，u9=min10，12， =10= u6 点点v6得永久标号，得永久标号， 6=5 ，X6=v1，v4 ，v3 ， v2， v5，v7 ，v6，X6=v8 ，v9，点点v8，v9临时标号不变。临时标号不变。 K=5 +1=6 mi

16、nu8，u9=min12， =12= u8 点点v8得永久标号，得永久标号， 8=5 ， 即从即从v1到到v8的最短路长为的最短路长为u8=12， 8=5 ， 5=2 ， 2=3 ， 3=1 ， 知从知从v1到到v8 的最短路为：的最短路为： P1，8=P（v1，v3 ， v2， v5，v8）v2v523464v3v1v4v6121061210v8v9v72363问题：本例中，问题：本例中，v1到到v9的最短路？的最短路？无向网络无向网络:负权弧时负权弧时。wijvivjwijwijvjvi无向网络中，最短路无向网络中，最短路最短链最短链。多个点对之间最短路？多个点对之间最短路？v1v2v31

17、2-3Dijkstra算法失效算法失效 void init () int i, j; for (i = 1; i = n; i+) /i=j的时候也可以初始化为0，只是有时候不合适 for (j = 1; j = n; j+) mappij = inf; void dijk (int u) int i, j, mins, v; for (i = 1; i = n; i+) disti = mappui; marki = false; marku = true; distu = 0; while (1) mins = inf; for (j = 1; j = n; j+) if (!markj

18、& distj mins) mins = distj, v = j; if (mins = inf) break; markv = true; for (j = 1; j = n; j+) if (!markj & distv + mappvj distj) distj = distv + mappvj; 三、三、Floyd算法算法 网络网络G=（V，A，W），令），令D=(dij)n n， 表示表示G中中vi到到vj的最短路的长度。的最短路的长度。iju 考虑考虑G中任意两点中任意两点vi，vj，如将，如将G中中vi，vj以外的点以外的点都删掉，得只剩都删掉，得只剩vi，vj

19、的一个子网络的一个子网络G0，记，记否则当 A, ij(0)ijjivvwdwij为弧（为弧（ vi，vj）的权。）的权。 在在G0中加入中加入v1及及G中与中与vi，vj，v1相相关联的弧，得关联的弧，得G1，G1中中vi到到vj的最短路的最短路长记为长记为 ,则一定有则一定有(1)ijd(0)j1(0)1i(0)(1) ,min ddddijijvivjv1wij 再在再在D1中加入中加入v2及及D中与中与vi，vj，v1， v2相关联的相关联的弧，得弧，得D2，D2中中vi到到vj的最短路长记为的最短路长记为 ，则有，则有(2)iju (1)2(1)2(1)(2) min jiijiju

20、u,uu 递推，递推，D中中n个点逐个加入子网络，终得个点逐个加入子网络，终得D中中vi到到vj的最短路路长的最短路路长 (n) ijijuu 如果计算结果希望给出具体的最短路的路径，如果计算结果希望给出具体的最短路的路径，则构造路径矩阵则构造路径矩阵S=(sij) n n , sij表示表示vi到到vj的最短路的的最短路的第一条弧的终点第一条弧的终点。如。如 ，则从，则从vi到到vj的最短路的最短路的第一条弧为（的第一条弧为（ vi，vt），第二条弧为从），第二条弧为从vt到到vj的的最短路的第一条弧。最短路的第一条弧。tsij)n( 有时候需要初始化有时候需要初始化 for ( int k

21、 = 0; k 节点个数节点个数; +k )for ( int i = 0; i 节点个数节点个数; +i )for ( int j = 0; j 节点个数节点个数; +j )if ( Disik + Diskj Disij )Disij = Disik + Diskj; 时间复杂度为时间复杂度为O(n3) 弗洛伊德弗洛伊德算法代码算法代码 Floyd算法步骤：算法步骤：第第1步：步： )1,2,., ;1,2,.,( , )(S UU (0)(0)(0)(0)njnijssijnnij 第第2步：计算步：计算)1,2,3,.,( S )1,2,3,.,( U )()()()(nk)s(nk)

22、u(nnkijknnkijk 其中其中1)-k(j1)-(ik)1k(ij1)-k(1)-k(kj1)-k(ik)1(ij1)-k(ij)k(ij1(1)-k(ik1)-k(ij)( uu u s u ,uminu kkikk)k-kjkijuuu ssu当 )(S )()(nnnijns , )( Unn)n(ij(n) u第第3步：当步：当k=n时，时，)n(ijs是是vi到到 vj最短路第一条弧的终点。最短路第一条弧的终点。是是vi到到 vj最短路路长。最短路路长。 niju 例例 求如下网络中各点对间最短路的路长。求如下网络中各点对间最短路的路长。v2v52-344v3v1v4-265

23、8解：解： 0240842036050D (0) 5432154321543215432154321S (0) 用用U(0)的第一行、第的第一行、第一列来修正其余的一列来修正其余的uij，即，即作作(0)j1(0)1i(0)(1) ,minddddijijmin ，4+5同时，在修正同时，在修正 处修改处修改(1) iju(0)1(1) ijiSS 54315431543215432154321S (1)0240842036050D (0)029408942036050D (1) 5432154321543215432154321S (0)1)0(41)1(42 ss11与与v4到到v1的第的

24、第一段一段弧相弧相同同用用U（1）的第二行、第二列修正其余的的第二行、第二列修正其余的uij，029408942036050D (1) 5431154311543215432154321S (1)021594608942036021150D (2) 541143115432154321421S (2)vivjv1v22)1(12)2(13 ss2211与与v1到到v2的第一的第一段弧相段弧相同同021594608942036021150D (2) 5411114311543215432124221S (2)用用U(2)第三行、第三列修正其余的第三行、第三列修正其余的iju02159460894

25、2036021150D (3) 5411114311543215432124221S (3) 5411114311543215432124221S (3)021594608942036021150D (3)用用U(3)第四行、第四列修正其余的第四行、第四列修正其余的iju02672608942036021150D (4) 5414311543215432124221S (4)4 4 4 4354451 ss02672608942036021150D (4) 5444414311543215432124221S (4)用用U(4)第五行、第五列修正其余的第五行、第五列修正其余的iju026726

26、0894200943530120850D (5) 54444143115352221S (5) 2)4(15513 ss2 5)4(35531 ss5255555从从v1到到v3的最短路长度的最短路长度 。 8d (5)13从从v5到到v2的最短路长度的最短路长度 7 (5)52d0267260894200943530120850D (5) 5444414311553555552522221S (5)路径路径： ,s2513 v1到到v3的最短路路经为的最短路路经为:P13=P(v1, v2, v5, v4, v3)路径路径： , 2, 1, 4512542552 sssv5到到v2的最短路路

27、经为的最短路路经为:P52=P(v5, v4, v1, v2),s5)5(23 ,s4)5(53 3)5(43 sv1v2v5v4 v3四、四、Ford算法（算法（Bellman-Ford）算法思想：逐次逼近算法思想：逐次逼近每次逼近是求每次逼近是求D中从顶点中从顶点V1到其余各点的带有限制的最短路。到其余各点的带有限制的最短路。第一次：自顶点到vj由一条弧组成的路中找一条最短的第二次：自顶点到vj由不多于两条弧组成的路中找一条最短的第m次：自顶点到vj由不多于m条弧组成的路中找一条最短的最多进行n-1次逼近定理：设网络D不含负回路，pj(m)是D的自顶点v1到顶点vj由不多于m条弧组成的路中

28、长度最小者，w(pj(m)=uj(m)，j=2,3,n,则对于一切2 j n,有uj(1)uj(m)=w1jminuk(m-1)+ wkj1 k n2 m n-1算法步骤：算法步骤：令 l(v1)=0,l(vj)=1(2 j n); m=1,u1(m)=0，uj(m)=w1j (2 j n)。步骤0步骤2 若m+1=n-1，结束。若m+1n-1，置m=m+1，转步骤，转步骤1 步骤1 对于一切2 j n，计算minuk(m)+ wkj1 k n。设minuk (m)+ wkj1 k n=ur(m)+wrj令uj(m+1)=ur(m)+wrj及l(vj)=l(vj)r若r=j其它v1v4v5v3

29、v22251-433l(v1)=0, l(vj)=1 (j=2,3,4,5)3, 5, 1, 0) 1 (5) 1 (4) 1 (3) 1 (2) 1 (1uuuuu1)( l , 1222) 1 (2)2(2uwuu3)( l , 1555)3(5)4(5uwuu5)( l , 6454) 1 (5)2(4uwuu3)( l , 1535) 1 (3)2(5uwuu1)( l , 1222)2(2)3(2uwuu2)( l , 3233)2(3)3(3uwuu5)( l , 4454)2(5)3(4uwuu3)( l , 1535)2(3)3(5uwuu1)( l , 1222)3(2)4(

30、2uwuu2)( l , 3333)3(3)4(3uwuu5)4( l , 254)3(5)4(4uwuu2)( l , 3323) 1 (2)2(3uwuubool Bellman_Ford(int s)for(int i = 1; i = n; +i) /初始化初始化disti = (i = s ? 0 : INF);for(int i = 1; i = n - 1; +i)for(int j = 1; j distedgej.u + edgej.cost) /松弛（松弛（顺序一定不能反顺序一定不能反）distedgej.v = distedgej.u + edgej.cost;preed

31、gej.v = edgej.u;for(int i = 1; i distedgei.u + edgei.cost)return 0;return 1;求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。SPFA算法是西南交通大学段凡丁于1994年发表的.很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估