bellman-ford算法

1、1：為了能夠求解邊上帶有負(fù)值的單源最短路徑問(wèn)題，為了能夠求解邊上帶有負(fù)值的單源最短路徑問(wèn)題，Bellman(貝爾曼貝爾曼)和和Ford(福福特特)提出了提出了的方法。的方法。的的：要求圖中不能包含要求圖中不能包含()，如下圖所示。，如下圖所示。20117-2(c)Bellman-Ford算法2Bellman-Ford算法思想構(gòu)造一個(gè)最短路徑長(zhǎng)度數(shù)組序列構(gòu)造一個(gè)最短路徑長(zhǎng)度數(shù)組序列dist 1 u, dist 2 u, , dist n-1 u。其中：其中：為從源點(diǎn)為從源點(diǎn)v到終點(diǎn)到終點(diǎn)u的只經(jīng)過(guò)一條邊的最短路徑長(zhǎng)度，并有的只經(jīng)過(guò)一條邊的最短路徑長(zhǎng)度，并有dist 1 u =Edgevu；為從源

2、點(diǎn)為從源點(diǎn)v到達(dá)終點(diǎn)到達(dá)終點(diǎn)u的最短路徑長(zhǎng)度；的最短路徑長(zhǎng)度；為從源點(diǎn)為從源點(diǎn)v出發(fā)出發(fā)到達(dá)終點(diǎn)到達(dá)終點(diǎn)u的最短的最短路徑長(zhǎng)度；路徑長(zhǎng)度；為從源點(diǎn)為從源點(diǎn)v出發(fā)出發(fā)到達(dá)終點(diǎn)到達(dá)終點(diǎn)u的最的最短路徑長(zhǎng)度；短路徑長(zhǎng)度；算法的最終目的是計(jì)算出算法的最終目的是計(jì)算出dist n-1 u，為源點(diǎn)，為源點(diǎn)v到頂點(diǎn)到頂點(diǎn)u的最短路徑長(zhǎng)度。的最短路徑長(zhǎng)度。3 dist k u。v設(shè)已經(jīng)求出設(shè)已經(jīng)求出 , u = 0, 1, , n-1，此即從源點(diǎn)，此即從源點(diǎn)v最多經(jīng)過(guò)不構(gòu)成最多經(jīng)過(guò)不構(gòu)成的的k-1條邊到達(dá)終點(diǎn)條邊到達(dá)終點(diǎn)u的最短路徑的長(zhǎng)度。的最短路徑的長(zhǎng)度。v從圖的鄰接矩陣可以找到各個(gè)頂點(diǎn)從圖的鄰接矩陣可以找

3、到各個(gè)頂點(diǎn)j到達(dá)頂點(diǎn)到達(dá)頂點(diǎn)u的距離的距離Edgeju，計(jì)算，計(jì)算，可得從源點(diǎn)，可得從源點(diǎn)v，最多經(jīng)過(guò)不構(gòu)，最多經(jīng)過(guò)不構(gòu)成成的的k條邊到達(dá)終點(diǎn)條邊到達(dá)終點(diǎn)u的最短路徑的長(zhǎng)度。的最短路徑的長(zhǎng)度。v比較比較和和，取較小者作為，取較小者作為dist k u的值。的值。遞推公式遞推公式(求頂點(diǎn)求頂點(diǎn)u到源點(diǎn)到源點(diǎn)v的最短路徑的最短路徑)： = = min , , j=0,1,n-1,ju4461230565-2-25-1-1133(c)6543210030301021021055606 5 4 3 2 1 0 kdist k 0dist k 1dist k 2dist k 3 dist k 4dist

4、 k 5dist k 61065520530354401354501350460135043 = min , = min6, mindist10+Edge01, dist12+Edge21, 5#define MAX_VER_NUM 10/頂點(diǎn)個(gè)數(shù)最大值頂點(diǎn)個(gè)數(shù)最大值#define MAX 1000000int EdgeMAX_VER_NUMMAX_VER_NUM; /圖的鄰接矩陣圖的鄰接矩陣int vexnum;/頂點(diǎn)個(gè)數(shù)頂點(diǎn)個(gè)數(shù)void BellmanFord(int v) /假定圖的鄰接矩陣和頂點(diǎn)個(gè)數(shù)已經(jīng)讀進(jìn)來(lái)了假定圖的鄰接矩陣和頂點(diǎn)個(gè)數(shù)已經(jīng)讀進(jìn)來(lái)了int i, k, u;for(i=0

5、; ivexnum; i+)disti=Edgevi;/對(duì)對(duì)dist 初始化初始化if( i!=v & disiMAX ) pathi = v;/對(duì)對(duì)path 初始化初始化else pathi = -1;1.本算法使用同一個(gè)數(shù)組本算法使用同一個(gè)數(shù)組來(lái)存放一系列的來(lái)存放一系列的 。其中其中k = 0, 1, , n-1。算法結(jié)束時(shí)中存放的是。算法結(jié)束時(shí)中存放的是 。數(shù)組含義同數(shù)組含義同中的中的數(shù)組。數(shù)組。6for(k=2; kvexnum; k+) /從從dist1u遞推出遞推出dist2u, ,distn-1ufor(u=0; u vexnum; u+)/修改每個(gè)頂點(diǎn)的修改每個(gè)頂點(diǎn)的distu

6、和和pathuif( u != v )for(i=0; ivexnum; i+)/考慮其他每個(gè)頂點(diǎn)考慮其他每個(gè)頂點(diǎn)if( Edgeiudisti+Edgeiu )distu=disti+Edgeiu;pathu=i;如果dist 各元素的初值為MAX，則循環(huán)應(yīng)該n-1次，即k的初值應(yīng)該改成1。7Dijkstra算法與Bellman算法的區(qū)別Dijkstra算法和Bellman算法思想有很大的區(qū)別：Dijkstra算法在求解過(guò)程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到T集合中各頂點(diǎn)的最短路徑長(zhǎng)度。Bellman算法在求解過(guò)程中，每次循環(huán)都要修改所有頂點(diǎn)的dis

7、t ，也就是說(shuō)源點(diǎn)到各頂點(diǎn)最短路徑長(zhǎng)度一直要到Bellman算法結(jié)束才確定下來(lái)。8在求出在求出distn-1 之后，再對(duì)每條邊之后，再對(duì)每條邊判斷一下：加入這條判斷一下：加入這條邊是否會(huì)使得頂點(diǎn)邊是否會(huì)使得頂點(diǎn)v的最短路徑值再縮短，即判斷：的最短路徑值再縮短，即判斷：distu+w(u,v)distv是否成立，如果成立，則說(shuō)明存在從源點(diǎn)可達(dá)的是否成立，如果成立，則說(shuō)明存在從源點(diǎn)可達(dá)的。代碼如。代碼如下：下：for (i=0;in;i+)for (j=0;jn;j+)if (Edgeijdisti+Edgeij)return 0;/存在從源點(diǎn)可達(dá)的負(fù)權(quán)值回路存在從源點(diǎn)可達(dá)的負(fù)權(quán)值回路return

8、 1;9假設(shè)圖的頂點(diǎn)個(gè)數(shù)為n，邊的個(gè)數(shù)為e。算法中有一個(gè)三重嵌套的for循環(huán)，如果：使用鄰接矩陣存儲(chǔ)圖，最內(nèi)層if語(yǔ)句的總執(zhí)行次數(shù)為O(n3)，因此算法的復(fù)雜度為O(n3)；使用鄰接表存儲(chǔ)圖，內(nèi)層的兩個(gè)for循環(huán)改成while循環(huán)，可以使算法的復(fù)雜度降為O(n*e)。10Bellman-Ford算法思想的另一種理解前面已經(jīng)提到：如果使用鄰接表存儲(chǔ)圖，內(nèi)層的兩個(gè)前面已經(jīng)提到：如果使用鄰接表存儲(chǔ)圖，內(nèi)層的兩個(gè)for循環(huán)改成循環(huán)改成while循環(huán)，可以使算法的復(fù)雜度降為循環(huán)，可以使算法的復(fù)雜度降為O(n*e)。而。而。：對(duì)圖中的每條有向邊：對(duì)圖中的每條有向邊，權(quán)值為，權(quán)值為w，如果，如果distu+

9、wdistv，即，即，那么應(yīng)該修改，那么應(yīng)該修改distv，修改成，修改成distu+w。11MAX 999999 EDGE_MAX 100 /邊數(shù)最大值邊數(shù)最大值 VER_MAX 50/頂點(diǎn)個(gè)數(shù)最大值頂點(diǎn)個(gè)數(shù)最大值 Edge u, v, w;/邊：起點(diǎn)、終點(diǎn)、權(quán)值邊：起點(diǎn)、終點(diǎn)、權(quán)值;Edge edgesEDGE_MAX;/存儲(chǔ)所有的邊存儲(chǔ)所有的邊 m;/實(shí)際邊的個(gè)數(shù)實(shí)際邊的個(gè)數(shù) n;/頂點(diǎn)個(gè)數(shù)頂點(diǎn)個(gè)數(shù)/* dist為源點(diǎn)為源點(diǎn)v0到各頂點(diǎn)的最短距離到各頂點(diǎn)的最短距離,如果初始為如果初始為v0到各頂點(diǎn)直接邊的長(zhǎng)度到各頂點(diǎn)直接邊的長(zhǎng)度,則則算法中的循環(huán)要執(zhí)行算法中的循環(huán)要執(zhí)行n-2次，如果初始

10、為次，如果初始為MAX，則循環(huán)要執(zhí)行，則循環(huán)要執(zhí)行n-1次，第一次求得的次，第一次求得的dist就是就是v0到各頂點(diǎn)直接邊的長(zhǎng)度到各頂點(diǎn)直接邊的長(zhǎng)度*/ distVER_MAX=MAX; /假定邊的數(shù)組、邊的個(gè)數(shù)這些信息已經(jīng)讀進(jìn)來(lái)了假定邊的數(shù)組、邊的個(gè)數(shù)這些信息已經(jīng)讀進(jìn)來(lái)了假設(shè)圖中有關(guān)邊的數(shù)據(jù)結(jié)構(gòu)如下：假設(shè)圖中有關(guān)邊的數(shù)據(jù)結(jié)構(gòu)如下：12bool bellman_ford()/bellman-ford算法算法int i, k, t;for(i = 1; i n; i +)/*假設(shè)第假設(shè)第k條邊的起點(diǎn)是條邊的起點(diǎn)是u,終點(diǎn)是終點(diǎn)是v,以下循環(huán)考慮第以下循環(huán)考慮第k條邊是否會(huì)使得源點(diǎn)條邊是否會(huì)使得源點(diǎn)v0到到v的的最短距離縮短最短距離縮短,即判斷即判斷distedgesk.u + edgesk.w distedgesk.v 是否成立是否成立*/for(k = 0; k m; k +)t = distedgesk.u + edgesk.w;if(distedgesk.u != mx & t distedgesk.v)distedgesk.v = t;/*以下是檢查，若還有更新則說(shuō)明存在無(wú)限循環(huán)的負(fù)值回路以下是檢查，若還有更新則說(shuō)明存在無(wú)限循環(huán)的負(fù)值回路*/for(k = 0; k m; k +)if(d