一、Bellman-Ford算法：
為了能夠求解邊上帶有負(fù)值的單源最短路徑問題，Bellman(貝爾曼)和Ford(福特)提出了從源點(diǎn)逐次繞過其他頂點(diǎn)，以縮短到達(dá)終點(diǎn)的最短路徑長度的方法。
Bellman-ford算法是求解連通帶權(quán)圖中單源最短路徑的一種常用算法，它允許圖中存在權(quán)值為負(fù)的邊。 同時(shí)它還能夠判斷出圖中是否存在一個(gè)權(quán)值之和為負(fù)的回路。如果存在的話，圖中就不存在最短路徑(因?yàn)?，假設(shè)存在最短路徑的話，那么我們只要將這條最短路徑沿著權(quán)值為負(fù)的環(huán)路再繞一圈，那么這條最短路徑的權(quán)值就會(huì)減少了，所以不存在最短的路徑，因?yàn)槁窂降淖钚≈禐樨?fù)無窮），如果不存在的話，那么求出源點(diǎn)到所有節(jié)點(diǎn)的最短路徑。
二、Bellman-Ford算法的限制條件：
要求圖中不能包含權(quán)值總和為負(fù)值回路(負(fù)權(quán)值回路)，如下圖所示。
三、Bellman-Ford算法思想
四、圖例
五：算法實(shí)現(xiàn)
static final int MAX=99999;int Edge[][]; //圖的鄰接矩陣int vexnum; //頂點(diǎn)個(gè)數(shù) private void BellmanFord(int v) {//假定圖的鄰接矩陣和頂點(diǎn)個(gè)數(shù)已經(jīng)讀進(jìn)來了 int i, k, u; for(i=0; i< vexnum; i++){ dist[i]=Edge[v][i]; //對dist[]初始化 if( i!=v && dis[i]< MAX ) path[i] = v;//對path[ ]初始化 else path[i] = -1; } //如果dist[]各元素的初值為MAX，則循環(huán)應(yīng)該n-1次，即k的初值應(yīng)該改成1。 for(k=2; k< vexnum; k++){ //從dist(1)[u]遞推出dist(2)[u], …,dist(n-1)[u] for(u=0; u< vexnum; u++){//修改每個(gè)頂點(diǎn)的dist[u]和path[u] if( u != v ) { for(i=0; i< vexnum; i++){//考慮其他每個(gè)頂點(diǎn) if( Edge[i][u]< MAX &&dist[u]>dist[i]+Edge[i][u] ){ dist[u]=dist[i]+Edge[i][u]; path[u]=i; } } } } } } 五、Dijkstra算法與Bellman算法的區(qū)別
Dijkstra算法和Bellman算法思想有很大的區(qū)別：
Dijkstra算法在求解過程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到T集合中各頂點(diǎn)的最短路徑長度。
Bellman算法在求解過程中，每次循環(huán)都要修改所有頂點(diǎn)的dist[]，也就是說源點(diǎn)到各頂點(diǎn)最短路徑長度一直要到Bellman算法結(jié)束才確定下來。
如果存在從源點(diǎn)可達(dá)的負(fù)權(quán)值回路，則最短路徑不存在，因?yàn)榭梢灾貜?fù)走這個(gè)回路，使得路徑無窮小。 在Bellman算法中判斷是否存在從源點(diǎn)可達(dá)的負(fù)權(quán)值回路的方法：
for (i=0;i< n;i++){ for (j=0;j< n;j++){ if (Edge[i][j]< MAX && dist[j]>dist[i]+Edge[i][j]) return false;//存在從源點(diǎn)可達(dá)的負(fù)權(quán)值回路 } } return true; 下載Bellman-Ford算法PPT
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點(diǎn)擊舉報(bào)。
