最短路問題DijkstraFloyd算法

1、 最短路問題最短路問題 趙嘉誠趙嘉誠Dijkstra算法算法Ford算法算法Floyd算法算法SPFA算法算法一、什么是最短路問題一、什么是最短路問題例例 下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條 線所需的費用?，F(xiàn)在某人要從線所需的費用。現(xiàn)在某人要從v1出發(fā)，通過這個交出發(fā)，通過這個交 通網(wǎng)到通網(wǎng)到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= 旅行路線總費用旅行路線總費用 路上所有弧權(quán)之和。路上所有弧權(quán)之和。最短路問題中，不考慮有向環(huán)、并行弧。最短路問題中，不考慮有向環(huán)、并行弧。即即適用于適用于DAG（有向無環(huán)圖）（有向無環(huán)圖）v2v523464v3v1v4v6121061210v8v9v72363最短路問題嚴格的定義最短路問題嚴格的定義 給定有向網(wǎng)絡(luò)給定有向網(wǎng)絡(luò)D=（V(點點)，A（弧），（?。?，W（權(quán)），任意?。?quán)），任意弧aijA，有權(quán)，有權(quán)w（ aij ）=wij，給定，給定D中的兩個頂點中的兩個頂點A，B。設(shè)。設(shè)P是是D中從中從A到到B的一條路，的一條路，定義路定義

3、路P的權(quán)（長度）是的權(quán)（長度）是P中所有弧的權(quán)之和，記為中所有弧的權(quán)之和，記為w（P）。最短路問題就是要在所有從）。最短路問題就是要在所有從vs到到vt的路中，求的路中，求一條路一條路P0 ，使，使(P)min)(PP0ww 稱稱P0是從是從vs到到vt的最短路。路的最短路。路P0的權(quán)稱為從的權(quán)稱為從vs到到vt的路長。記為的路長。記為ust。 最短路徑問題是圖論研究中的一個經(jīng)典算法問最短路徑問題是圖論研究中的一個經(jīng)典算法問題，題， 旨在尋找圖（由結(jié)點和路徑組成的）中兩旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。結(jié)點之間的最短路徑。 算法具體的形式包括：算法具體的形式包括： 確定起

4、點的最短路徑問題確定起點的最短路徑問題 - 即已知起始結(jié)點，即已知起始結(jié)點，求最短路徑的問題。求最短路徑的問題。 確定終點的最短路徑問題確定終點的最短路徑問題 - 與確定起點的問題與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。方向反轉(zhuǎn)的確定起點的問題。 確定起點終點的最短路徑問題確定起點終點的最短路徑問題 - 即已知起點和即已知起點和終點，求兩結(jié)點之間的最短路徑

5、。終點，求兩結(jié)點之間的最短路徑。 全局最短路徑問題全局最短路徑問題 - 求圖中所有的最短路徑求圖中所有的最短路徑。二、二、Dijkstra（迪杰特斯拉）算法（迪杰特斯拉）算法 當(dāng)所有當(dāng)所有 wij 0 時，時，本算法是用來本算法是用來求給定點求給定點vs到到任一個點任一個點vj 最短路最短路的公認的最好方法。的公認的最好方法。事實：如果事實：如果P是是D中從中從vs到到vj的最短路，的最短路，vi是是P中的一中的一個點，那么，從個點，那么，從vs沿沿P到到vi的路是從的路是從vs到到 vi的最短路。的最短路。 最短路的子路也是最短路。最短路的子路也是最短路。DijkstraDijkstra算法

6、是典型的最短路徑路由算法，用于算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展特點是以起始點為中心向外層層擴展，直到擴展到終點為止。到終點為止。DijkstraDijkstra算法能得出最短路徑的最算法能得出最短路徑的最優(yōu)解，優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率但由于它遍歷計算的節(jié)點很多，所以效率低。低。 思想：將思想：將D=（V，A，W）中）中vs到所有其它頂點的最短到所有其它頂點的最短 路按其路按其路長路長從小到大排列為：從小到大排列為：u0 u1 u2 unu0表示表示v

7、s到自身的長度，相應(yīng)最短路記為：到自身的長度，相應(yīng)最短路記為：P0，P1，P2，Pn， sivswuvi0X1000min , XVX ,X則記取最小值的點為取最小值的點為v1， P1=P（vs，v1） 假定假定 u0，u1，uk的值已求出，對應(yīng)的最短路的值已求出，對應(yīng)的最短路分別為分別為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 的最短路長度，相應(yīng)的的最短路長度，相應(yīng)的點記點記“永久永久”標號；標號； XK中的點，中的點，ui值是值是vs到到vi的最短路長度的上界，的最短路長度的上界，相應(yīng)的點記相應(yīng)的點記“臨時臨時”標號，供進一步計算使用。標號，供進一步計算使用。前點標號前點標號 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中各點沒有路；否則，轉(zhuǎn)第中各點沒有路；否則，轉(zhuǎn)第3步。步。如果如果Xk+1 = ，結(jié)束

12、，到所有的點的最短路已經(jīng)求結(jié)束，到所有的點的最短路已經(jīng)求得得 ；否則，轉(zhuǎn)第；否則，轉(zhuǎn)第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的最短路？的最短路？無向網(wǎng)絡(luò)無向網(wǎng)絡(luò):負權(quán)弧時負權(quán)弧時。wijvivjwijwijvjvi無向網(wǎng)絡(luò)中，最短路無向網(wǎng)絡(luò)中，最短路最短鏈最短鏈。多個點對之間最短路？多個點對之間最短路？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算法算法 網(wǎng)絡(luò)網(wǎng)絡(luò)G=（V，A，W），令），令D=(dij)n n， 表示表示G中中vi到到vj的最短路的長度。的最短路的長度。iju 考慮考慮G中任意兩點中任意兩點vi，vj，如將，如將G中中vi，vj以外的點以外的點都刪掉，得只剩都刪掉，得只剩vi，vj

19、的一個子網(wǎng)絡(luò)的一個子網(wǎng)絡(luò)G0，記，記否則當(dāng) A, ij(0)ijjivvwdwij為?。榛。?vi，vj）的權(quán)。）的權(quán)。 在在G0中加入中加入v1及及G中與中與vi，vj，v1相相關(guān)聯(lián)的弧，得關(guān)聯(lián)的弧，得G1，G1中中vi到到vj的最短路的最短路長記為長記為 ,則一定有則一定有(1)ijd(0)j1(0)1i(0)(1) ,min ddddijijvivjv1wij 再在再在D1中加入中加入v2及及D中與中與vi，vj，v1， v2相關(guān)聯(lián)的相關(guān)聯(lián)的弧，得弧，得D2，D2中中vi到到vj的最短路長記為的最短路長記為 ，則有，則有(2)iju (1)2(1)2(1)(2) min jiijiju

20、u,uu 遞推，遞推，D中中n個點逐個加入子網(wǎng)絡(luò)，終得個點逐個加入子網(wǎng)絡(luò)，終得D中中vi到到vj的最短路路長的最短路路長 (n) ijijuu 如果計算結(jié)果希望給出具體的最短路的路徑，如果計算結(jié)果希望給出具體的最短路的路徑，則構(gòu)造路徑矩陣則構(gòu)造路徑矩陣S=(sij) n n , sij表示表示vi到到vj的最短路的的最短路的第一條弧的終點第一條弧的終點。如。如 ，則從，則從vi到到vj的最短路的最短路的第一條弧為（的第一條弧為（ vi，vt），第二條弧為從），第二條弧為從vt到到vj的的最短路的第一條弧。最短路的第一條弧。tsij)n( 有時候需要初始化有時候需要初始化 for ( int k

21、 = 0; k 節(jié)點個數(shù)節(jié)點個數(shù); +k )for ( int i = 0; i 節(jié)點個數(shù)節(jié)點個數(shù); +i )for ( int j = 0; j 節(jié)點個數(shù)節(jié)點個數(shù); +j )if ( Disik + Diskj Disij )Disij = Disik + Diskj; 時間復(fù)雜度為時間復(fù)雜度為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當(dāng) )(S )()(nnnijns , )( Unn)n(ij(n) u第第3步：當(dāng)步：當(dāng)k=n時，時，)n(ijs是是vi到到 vj最短路第一條弧的終點。最短路第一條弧的終點。是是vi到到 vj最短路路長。最短路路長。 niju 例例 求如下網(wǎng)絡(luò)中各點對間最短路的路長。求如下網(wǎng)絡(luò)中各點對間最短路的路長。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的最短路路經(jīng)為的最短路路經(jīng)為:P13=P(v1, v2, v5, v4, v3)路徑路徑： , 2, 1, 4512542552 sssv5到到v2的最短路路

27、經(jīng)為的最短路路經(jīng)為: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次逼近定理：設(shè)網(wǎng)絡(luò)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，結(jié)束。若m+1n-1，置m=m+1，轉(zhuǎn)步驟，轉(zhuǎn)步驟1 步驟1 對于一切2 j n，計算minuk(m)+ wkj1 k n。設(shè)minuk (m)+ wkj1 k n=ur(m)+wrj令uj(m+1)=ur(m)+wrj及l(fā)(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算法是西南交通大學(xué)段凡丁于1994年發(fā)表的.很多時候，給定的圖存在負權(quán)邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，SPFA算法便派上用場了。我們用數(shù)組d記錄每個結(jié)點的最短路徑估計值，而且用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設(shè)立一個先進先出的隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，并且用u點當(dāng)前的最短路徑估計值對離開u點所指向的結(jié)點v進行松弛操作，如果v點的最短路徑估