Bellman-Ford算法--解決負權(quán)邊的單源最短路徑算法

2019-11-10 22:35:42

字體：大中小

供稿：網(wǎng)友

在http://blog.csdn.net/hacker_zhidian/article/details/54915152這篇博客中，我們用Dijkstra算法單源最短路徑，但是Dijkstra算法對于存在負權(quán)邊的圖就無能為力了，接下來就是Bellman-Ford算法顯威的時候了，因為它能解決存在負權(quán)邊的圖中的單源最短路徑問題。Bellman-Ford算法的核心思想是：對圖中所有的邊進行縮放，每一次縮放更新單源最短路徑。我們依然通過一個例子來看：這里寫圖片描述假設(shè)存在這么一個有向圖。圖中有A 、B、C、D、E 五個頂點，有 A–>B（3）、A–>E（-2）、B–>D（5）、B–>C（2）、D–>C（1）、D–>E（4）這 6 條邊。假設(shè)現(xiàn)在我們要求頂點A到其他頂點的最短路徑，按照Bellman-Ford算法的思想：

我們要對所有的邊進行“縮放”，首先找到第一條邊：A–>B（3），那么對于頂點B，能不能通過頂點B使得頂點A到其他頂點的最短路徑變短呢，在這里我們可以找到A–>B（3）來使得頂點A到頂點B的最短路徑變短，于是我們更新頂點A到頂點B的最短路徑。接下來我們再找第二條邊，同樣的A–>E（-2）可以使得頂點A到頂點E的最短路徑變短，繼續(xù)更新頂點A到頂點E的最短路徑。重復剛剛的縮放過程。。。將所有的邊縮放完了之后，重復上面的縮放過程。那么什么時候縮放結(jié)束呢。最多在縮放了n-1輪（n為圖中頂點的總數(shù)）的時候就結(jié)束了（因為圖中兩個頂點中的邊最多有n-1條）。

其實Bellman-Ford算法和Dijkstra算法類似，都是縮放使得最短路徑變短，不同的是Dijkstra算法是對頂點進行縮放，Bellman-Ford算法是對邊進行縮放。既然是對邊進行縮放，那么我們就要儲存邊的信息，這里可以采用一個結(jié)構(gòu)體數(shù)組來儲存邊的信息。下面是Bellman-Ford算法的核心代碼：

for(int i = 1; i <= n - 1; i++) // 最多n - 1輪縮放{ for(int j = 1; j <= m; j++) // 每一輪對所有的邊進行縮放 { if(dis[edge[j].end] > dis[edge[j].start] + edge[j].weight) //edge是儲存邊的信息的結(jié)構(gòu)體 { dis[edge[j].end] = dis[edge[j].start] + edge[j].weight; // 如果這條邊能夠使得頂點A到這條邊結(jié)束的那個頂點的最短路徑變短，則更新最短路徑 } }}

理解了這個，下面就是簡單的收尾了，這里給出案例的完整代碼：

#include <iostream>using namespace std;const int N = 500; // 圖中最多有500個頂點const int inf = 999999999; // 無窮大，表示源點到其他頂點的初始最短路徑struct Edge // 儲存邊的信息的結(jié)構(gòu)體{ int start; // 邊的開始頂點 int end; // 邊的結(jié)束頂點 int weight; // 邊的權(quán)值};Edge edge[N*N]; // 最多250000條邊int dis[N]; // 儲存源點到其他頂點的最短路徑的數(shù)組int main(){ int n, m, s; // 圖中頂點的總數(shù)，邊的總數(shù)和源點 cin >> n >> m >> s; for(int i = 1; i <= m; i++) // 輸入圖中邊的信息 { cin >> edge[i].start >> edge[i].end >> edge[i].weight; } for(int i = 1; i <= n; i++) { dis[i] = inf; // 初始化源點到其他頂點的最短路徑 } dis[s] = 0; // Bellman-Ford算法的核心代碼： for(int i = 1; i <= n - 1; i++) // 最多n - 1輪縮放 { int check = 0; for(int j = 1; j <= m; j++) // 每一輪對所有的邊進行縮放 { if(dis[edge[j].end] > dis[edge[j].start] + edge[j].weight) //edge是儲存邊的信息的結(jié)構(gòu)體 { dis[edge[j].end] = dis[edge[j].start] + edge[j].weight; // 如果這條邊能夠使得源點到這條邊結(jié)束的那個頂點的最短路徑變短，則更新最短路徑 check = 1; } } if(check == 0) { break; // 如果這一輪的縮放沒有使得任何頂點到源點的最短路徑變短，那么就不用嘗試下一輪縮放了，因為下一輪縮放和這一輪縮放的原理和步驟是一樣的 } } for(int i = 1; i <= n; i++) //輸出結(jié)果 { cout << dis[i] << " "; } cout << endl; return 0;}

運行程序，輸入數(shù)據(jù)：這里寫圖片描述帶入給定的圖中進行檢查，確實是我們想要的答案。小伙伴們可以自己嘗試一下。 Bellman-Ford算法的時間復雜度為O(M*N)，但是我們這里可以對Bellman-Ford算法進行優(yōu)化：我們每一次縮放的時候如果圖中的某條邊確實使得源點到其他頂點的最短路徑變短，那么下一輪縮放只需要對上一輪縮放的時候使得源點到其他頂點最短路徑變短的邊的結(jié)束點的出邊（出度）進行縮放就行了（這句話有點難理解），因為下一輪縮放的原理和這一輪是一樣的。我們可以用一個隊列來儲存這些頂點，縮放的時候?qū)⑦@些頂點依次出隊，并且將新的符合要求的頂點入隊。直到隊列為空。這樣的話我們的Bellman-Ford算法在最壞的情況下時間復雜度也是O(M*N)。