貝爾曼-福特演算法
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
貝爾曼-福特演算法 | |
---|---|
概況 | |
類別 | 最短路徑問題(針對帶權有向圖) |
資料結構 | 圖 |
複雜度 | |
最壞時間複雜度 | |
最佳時間複雜度 | |
空間複雜度 | |
相關變數的定義 |
圖與樹 搜尋演算法 |
---|
分類 |
相關主題 |
貝爾曼-福特演算法(英語:Bellman–Ford algorithm),求解單源最短路徑問題的一種演算法,由理查德·貝爾曼和小萊斯特·倫道夫·福特創立。有時候這種演算法也被稱為貝爾曼-福特-摩爾演算法(Bellman–Ford–Moore algorithm),因為愛德華·F·摩爾也為這個演算法的發展做出了貢獻。它的原理是對圖進行次鬆弛操作,得到所有可能的最短路徑。其優於戴克斯特拉演算法的方面是邊的權值可以為負數、實現簡單,缺點是時間複雜度過高,高達。但演算法可以進行若干種最佳化,提高了效率。
演算法
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/85/Bellman-Ford_worst-case_example.svg/220px-Bellman-Ford_worst-case_example.svg.png)
貝爾曼-福特演算法與戴克斯特拉演算法類似,都以鬆弛操作為基礎,即估計的最短路徑值漸漸地被更加準確的值替代,直至得到最佳解。在兩個演算法中,計算時每個邊之間的估計距離值都比真實值大,並且被新找到路徑的最小長度替代。 然而,戴克斯特拉演算法以貪婪法選取未被處理的具有最小權值的節點,然後對其的出邊進行鬆弛操作;而貝爾曼-福特演算法簡單地對所有邊進行鬆弛操作,共次,其中是圖的點的數量。在重複地計算中,已計算得到正確的距離的邊的數量不斷增加,直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特演算法比戴克斯特拉演算法適用於更多種類的輸入。
貝爾曼-福特演算法的最多執行(大O符號)次,和分別是節點和邊的數量)。
偽代碼
[編輯]procedure BellmanFord(list vertices, list edges, vertex source) // 读入边和节点的列表 // 初始化图 distance为∞,predecessor为空 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 对所有节点 for i from 1 to size(vertices)-1: //检查每条边 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // 检查是否有负权重的回路 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "图包含负权重的回路"
原理
[編輯]迴圈
[編輯]每次迴圈操作實際上是對相鄰節點的訪問,第次迴圈操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過條邊,所以可知貝爾曼-福特演算法所得為最短路徑。
負邊權操作
[編輯]與戴克斯特拉演算法不同的是,戴克斯特拉演算法的基本操作「拓展」是在深度上尋路,而「鬆弛」操作則是在廣度上尋路,這就確定了貝爾曼-福特演算法可以對負邊進行操作而不會影響結果。
負權環判定
[編輯]因為負權環可以無限制的降低總花費,所以如果發現第次操作仍可降低花銷,就一定存在負權環。
尋找負迴路
[編輯]當使用這個演算法尋找最短路徑時,有負迴路會使演算法找不到正確的答案。但是,由於在找到負迴路後會中止演算法,所以可以被用來尋找目標,例如在網絡流分析中的消圈演算法(Cycle Cancellation Algorithms)
最佳化
[編輯]迴圈的提前跳出
[編輯]在實際操作中,貝爾曼-福特演算法經常會在未達到次前就出解,其實是最大值。於是可以在迴圈中設置判定,在某次迴圈不再進行鬆弛時,直接退出迴圈,進行負權環判定。
佇列最佳化
[編輯]西南交通大學的段凡丁於1994年提出了用佇列來最佳化的演算法。鬆弛操作必定只會發生在最短路徑前導節點鬆弛成功過的節點上,用一個佇列記錄鬆弛過的節點,可以避免了冗餘計算。原文中提出該演算法的複雜度為,是個比較小的係數,[1]但該結論被證明不適于于所有情況。[來源請求]
Pascal語言範例
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do
begin
u:=dequeue(Q);
for each v∈adj[u] do
begin
tmp:=d[v];
relax(u,v);
if (tmp<>d[v]) and (not v in Q) then
enqueue(Q,v);
end;
end;
End;
C++語言範例
int SPFA(int s) {
std::queue<int> q;
bool inq[maxn] = {false};
for(int i = 1; i <= N; i++) dis[i] = 2147483647;
dis[s] = 0;
q.push(s); inq[s] = true;
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = false;
for(int i = front[x]; i !=0 ; i = e[i].next) {
int k = e[i].v;
if(dis[k] > dis[x] + e[i].w) {
dis[k] = dis[x] + e[i].w;
if(!inq[k]) {
inq[k] = true;
q.push(k);
}
}
}
}
for(int i = 1; i <= N; i++) std::cout << dis[i] << ' ';
std::cout << std::endl;
return 0;
}
樣例
[編輯]例:
- ,。
執行如表:
點 | ||||
---|---|---|---|---|
初始化 | ||||
迴圈第一次 | ||||
迴圈第二次 | ||||
迴圈第三次 |
參考文獻
[編輯]
|