最短路問題DijkstraFloyd算法

1、 最短路問題最短路問題 趙嘉誠趙嘉誠Dijkstra算法算法Ford算法算法Floyd算法算法SPFA算法算法一、什么是最短路問題一、什么是最短路問題例例 下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條 線所需的費(fèi)用。現(xiàn)在某人要從線所需的費(fèi)用?，F(xiàn)在某人要從v1出發(fā)，通過這個(gè)交出發(fā)，通過這個(gè)交 通網(wǎng)到通網(wǎng)到v8去，求使總費(fèi)用最小的旅行路線。去，求使總費(fèi)用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363從從v1到到v8：P1=（v1，v2，v5，v8） 費(fèi)用費(fèi)用 6+1+6=13P2=（v1，v3，v4， v6， v

2、7， v8） 費(fèi)用費(fèi)用 3+2+10+2+4=21P3= 旅行路線總費(fèi)用旅行路線總費(fèi)用 路上所有弧權(quán)之和。路上所有弧權(quán)之和。最短路問題中，不考慮有向環(huán)、并行弧。最短路問題中，不考慮有向環(huán)、并行弧。即即適用于適用于DAG（有向無環(huán)圖）（有向無環(huán)圖）v2v523464v3v1v4v6121061210v8v9v72363最短路問題嚴(yán)格的定義最短路問題嚴(yán)格的定義 給定有向網(wǎng)絡(luò)給定有向網(wǎng)絡(luò)D=（V(點(diǎn)點(diǎn))，A（弧），（弧），W（權(quán)），任意?。?quán)），任意弧aijA，有權(quán)，有權(quán)w（ aij ）=wij，給定，給定D中的兩個(gè)頂點(diǎn)中的兩個(gè)頂點(diǎn)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。 最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題，題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。結(jié)點(diǎn)之間的最短路徑。 算法具體的形式包括：算法具體的形式包括： 確定起

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

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

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

7、s到自身的長度，相應(yīng)最短路記為：到自身的長度，相應(yīng)最短路記為：P0，P1，P2，Pn， sivswuvi0X1000min , XVX ,X則記取最小值的點(diǎn)為取最小值的點(diǎn)為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 使上式達(dá)到最小值的點(diǎn)使上式達(dá)到最小值的點(diǎn)v 可取為可取為vk+1。 計(jì)算過程中可采用標(biāo)

8、號方法。計(jì)算過程中可采用標(biāo)號方法。 Xk中的點(diǎn)，中的點(diǎn)，ui 值是值是vs 到到vi 的最短路長度，相應(yīng)的的最短路長度，相應(yīng)的點(diǎn)記點(diǎn)記“永久永久”標(biāo)號；標(biāo)號； XK中的點(diǎn)，中的點(diǎn)，ui值是值是vs到到vi的最短路長度的上界，的最短路長度的上界，相應(yīng)的點(diǎn)記相應(yīng)的點(diǎn)記“臨時(shí)臨時(shí)”標(biāo)號，供進(jìn)一步計(jì)算使用。標(biāo)號，供進(jìn)一步計(jì)算使用。前點(diǎn)標(biāo)號前點(diǎn)標(biāo)號 i : 表示點(diǎn)表示點(diǎn)vs到到vj的最短路上的最短路上vj的前一點(diǎn)。的前一點(diǎn)。如如 i=m，表示，表示vs到到vj的最短路上的最短路上vj前一點(diǎn)是前一點(diǎn)是vm。 6圖上標(biāo)號法圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v

9、60 1 36圖上標(biāo)號法圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60 1 36v5v223464v3v1v41210 6 1210v8v9v72363v60 111 3圖上標(biāo)號法圖上標(biāo)號法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60 111 36圖上標(biāo)號法圖上標(biāo)號法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60 111 35圖上標(biāo)號法圖上標(biāo)號法:5v5v223464v3v1v41210 6 1210v8v9v72363v60 111 3圖上標(biāo)號法圖上標(biāo)號法:5v5v2

10、23464v3v1v41210 6 1210v8v9v72363v60 111 36圖上標(biāo)號法圖上標(biāo)號法:5v5v223464v3v1v41210 6 1210v8v9v72363v6011163圖上標(biāo)號法圖上標(biāo)號法:5v5v223464v3v1v41210 6 1210v8v9v72363v6010161239圖上標(biāo)號法圖上標(biāo)號法:5v5v223464v3v1v41210 6 1210v8v9v72363v6010161239圖上標(biāo)號法圖上標(biāo)號法:Dijkstra算法步驟：算法步驟：第第1步：令步：令us= 0，uj=wsj （1jn）若）若asj A，則，則第第2步：步：(選永久標(biāo)號選永久

11、標(biāo)號)在在XK中選一點(diǎn)中選一點(diǎn)vi，滿足，滿足 第第3步：（給點(diǎn)步：（給點(diǎn)vi永久性標(biāo)號）永久性標(biāo)號） 第第4步：步：(修改臨時(shí)標(biāo)號修改臨時(shí)標(biāo)號)對所有對所有 如果如果 , 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中各點(diǎn)沒有路；否則，轉(zhuǎn)第中各點(diǎn)沒有路；否則，轉(zhuǎn)第3步。步。如果如果Xk+1 = ，結(jié)束

12、，到所有的點(diǎn)的最短路已經(jīng)求結(jié)束，到所有的點(diǎn)的最短路已經(jīng)求得得 ；否則，轉(zhuǎn)第；否則，轉(zhuǎn)第4步。步。例例 用用Dijkstra算法求前面例子中從算法求前面例子中從v1到各點(diǎn)的最短路。到各點(diǎn)的最短路。解：解：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 點(diǎn)點(diǎn)v4得永久標(biāo)號，得永久標(biāo)號， 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 修改臨時(shí)標(biāo)號修改臨時(shí)標(biāo)號u6= 11 ， 6=4 ，其余標(biāo)號不變。，其余標(biāo)號不變。v2v523464v3v1v4v6121061210v8v9v72363K=0 +1=1 minu2，u3，u5，u6，u7，u8，u9 =min6，3， ， 11， ， ， =3= u3 點(diǎn)點(diǎn)v3得永久標(biāo)號，得永久標(biāo)號， 3=1 ，X2=v1，v4 ，v3， X2=v2， v5，v6 ，v7，v8 ，v9， u2= 6 ，u3+w32=3+2=5， 即即 u3+w32

14、u2 修改臨時(shí)標(biāo)號修改臨時(shí)標(biāo)號u2= 5 ， 2=3 ，其余標(biāo)號不變。，其余標(biāo)號不變。在所有在所有vjX2中中， k=2 +1=3 minu5，u6，u7，u8，u9 =min6，11， ， ， =6= u5 點(diǎn)點(diǎn)v5得永久標(biāo)號，得永久標(biāo)號， 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 修改臨時(shí)標(biāo)號修改臨時(shí)標(biāo)號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 點(diǎn)點(diǎn)v7得永久標(biāo)號，得永久標(biāo)號， 7=5 ，X2=v1，v4 ，v3 ， v2， v5，v7，X2=v6 ，v8 ，v9，在在vjX5中，臨時(shí)標(biāo)號不變。中，臨時(shí)標(biāo)號不變。K=4 +1=5 minu6，u8，u9=min10，12， =10= u6 點(diǎn)點(diǎn)v6得永久標(biāo)號，得永久標(biāo)號， 6=5 ，X6=v1，v4 ，v3 ， v2， v5，v7 ，v6，X6=v8 ，v9，點(diǎn)點(diǎn)v8，v9臨時(shí)標(biāo)號不變。臨時(shí)標(biāo)號不變。 K=5 +1=6 mi

16、nu8，u9=min12， =12= u8 點(diǎn)點(diǎn)v8得永久標(biāo)號，得永久標(biāo)號， 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ò):負(fù)權(quán)弧時(shí)負(fù)權(quán)弧時(shí)。wijvivjwijwijvjvi無向網(wǎng)絡(luò)中，最短路無向網(wǎng)絡(luò)中，最短路最短鏈最短鏈。多個(gè)點(diǎn)對之間最短路？多個(gè)點(diǎn)對之間最短路？v1v2v31

17、2-3Dijkstra算法失效算法失效 void init () int i, j; for (i = 1; i = n; i+) /i=j的時(shí)候也可以初始化為0，只是有時(shí)候不合適 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中任意兩點(diǎn)中任意兩點(diǎn)vi，vj，如將，如將G中中vi，vj以外的點(diǎn)以外的點(diǎn)都刪掉，得只剩都刪掉，得只剩vi，vj

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

21、 = 0; k 節(jié)點(diǎn)個(gè)數(shù)節(jié)點(diǎn)個(gè)數(shù); +k )for ( int i = 0; i 節(jié)點(diǎn)個(gè)數(shù)節(jié)點(diǎn)個(gè)數(shù); +i )for ( int j = 0; j 節(jié)點(diǎn)個(gè)數(shù)節(jié)點(diǎn)個(gè)數(shù); +j )if ( Disik + Diskj Disij )Disij = Disik + Diskj; 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n3) 弗洛伊德弗洛伊德算法代碼算法代碼 Floyd算法步驟：算法步驟：第第1步：步： )1,2,., ;1,2,.,( , )(S UU (0)(0)(0)(0)njnijssijnnij 第第2步：計(jì)算步：計(jì)算)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時(shí)，時(shí)，)n(ijs是是vi到到 vj最短路第一條弧的終點(diǎn)。最短路第一條弧的終點(diǎn)。是是vi到到 vj最短路路長。最短路路長。 niju 例例 求如下網(wǎng)絡(luò)中各點(diǎn)對間最短路的路長。求如下網(wǎng)絡(luò)中各點(diǎn)對間最短路的路長。v2v52-344v3v1v4-265

23、8解：解： 0240842036050D (0) 5432154321543215432154321S (0) 用用U(0)的第一行、第的第一行、第一列來修正其余的一列來修正其余的uij，即，即作作(0)j1(0)1i(0)(1) ,minddddijijmin ，4+5同時(shí)，在修正同時(shí)，在修正 處修改處修改(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中從頂點(diǎn)中從頂點(diǎn)V1到其余各點(diǎn)的帶有限制的最短路。到其余各點(diǎn)的帶有限制的最短路。第一次：自頂點(diǎn)到vj由一條弧組成的路中找一條最短的第二次：自頂點(diǎn)到vj由不多于兩條弧組成的路中找一條最短的第m次：自頂點(diǎn)到vj由不多于m條弧組成的路中找一條最短的最多進(jìn)行n-1次逼近定理：設(shè)網(wǎng)絡(luò)D不含負(fù)回路，pj(m)是D的自頂點(diǎn)v1到頂點(diǎn)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，計(jì)算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ā)表的.很多時(shí)候，給定的圖存在負(fù)權(quán)邊，這時(shí)類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，SPFA算法便派上用場了。我們用數(shù)組d記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估