-
貝爾曼-福特算法
鎖定
- 中文名
- 貝爾曼-福特算法
- 外文名
- Bellman-Ford
- 創立人
- 理查德·貝爾曼和萊斯特·福特
- 也被稱為
- Moore-Bellman-Ford 算法
貝爾曼-福特算法算法簡介
貝爾曼-福特算法(英語:Bellman–Ford algorithm),求解單源最短路徑問題的一種算法,由理查德·貝爾曼(Richard Bellman) 和萊斯特·福特創立的。有時候這種算法也被稱為 Moore-Bellman-Ford 算法,因為Edward F. Moore也為這個算法的發展做出了貢獻。它的原理是對圖進行
次鬆弛操作,得到所有可能的最短路徑。其優於迪科斯徹算法的方面是邊的權值可以為負數、實現簡單,缺點是時間複雜度過高,高達
。但算法可以進行若干種優化,提高了效率。
貝爾曼-福特算法與迪科斯徹算法類似,都以鬆弛操作為基礎,即估計的最短路徑值漸漸地被更加準確的值替代,直至得到最優解。在兩個算法中,計算時每個邊之間的估計距離值都比真實值大,並且被新找到路徑的最小長度替代。 然而,迪科斯徹算法以貪心法選取未被處理的具有最小權值的節點,然後對其的出邊進行鬆弛操作;而貝爾曼-福特算法簡單地對所有邊進行鬆弛操作,共
次,其中
是圖的點的數量。在重複地計算中,已計算得到正確的距離的邊的數量不斷增加,直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特算法比迪科斯徹算法適用於更多種類的輸入。
貝爾曼-福特算法偽代碼表示
procedure BellmanFord(list vertices, list edges, vertex source) // 該實現讀入邊和節點的列表,並向兩個數組(distance和predecessor)中寫入最短路徑信息 // 步驟1:初始化圖 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 步驟2:重複對每一條邊進行鬆弛操作 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 // 步驟3:檢查負權環 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "圖包含了負權環"
貝爾曼-福特算法原理
貝爾曼-福特算法鬆弛
每次鬆弛操作實際上是對相鄰節點的訪問,第
次鬆弛操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過
條邊,所以可知貝爾曼-福特算法所得為最短路徑。
貝爾曼-福特算法負邊權操作
與迪科斯徹算法不同的是,迪科斯徹算法的基本操作“拓展”是在深度上尋路,而“鬆弛”操作則是在廣度上尋路,這就確定了貝爾曼-福特算法可以對負邊進行操作而不會影響結果。
貝爾曼-福特算法負權環判定
貝爾曼-福特算法優化
循環的提前跳出
在實際操作中,貝爾曼-福特算法經常會在未達到
次前就出解,
其實是最大值。於是可以在循環中設置判定,在某次循環不再進行鬆弛時,直接退出循環,進行負權環判定。
隊列優化
主條目:最短路徑快速算法
西南交通大學的段凡丁於1994年提出了用隊列來優化的算法。鬆弛操作必定只會發生在最短路徑前導節點鬆弛成功過的節點上,用一個隊列記錄鬆弛過的節點,可以避免了冗餘計算。原文中提出該算法的複雜度為
,
是個比較小的係數,但該結論未得到廣泛認可。
[2]
Pascal語言示例
Begin 2 initialize-single-source(G,s); 3 initialize-queue(Q); 4 enqueue(Q,s); 5 while not empty(Q) do 6 begin 7 u:=dequeue(Q); 8 for each v∈adj[u] do 9 begin 10 tmp:=d[v]; 11 relax(u,v); 12 if (tmp<>d[v]) and (not v in Q) then 13 enqueue(Q,v); 14 end; 15 end; 16 End;
C++語言示例
int SPFA(int s) { 2 queue<int> q; 3 bool inq[maxn] = {false}; 4 for(int i = 1; i <= N; i++) dis[i] = 2147483647; 5 dis[s] = 0; 6 q.push(s); inq[s] = true; 7 while(!q.empty()) { 8 int x = q.front(); q.pop(); 9 inq[x] = false; 10 for(int i = front[x]; i !=0 ; i = e[i].next) { 11 int k = e[i].v; 12 if(dis[k] > dis[x] + e[i].w) { 13 dis[k] = dis[x] + e[i].w; 14 if(!inq[k]) { 15 inq[k] = true; 16 q.push(k); 17 } 18 } 19 } 20 } 21 for(int i = 1; i <= N; i++) cout << dis[i] << ' '; 22 cout << endl; 23 return 0; 24 }
- 參考資料
-
- 1. Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Section 2.3.4: The Bellman-Ford-Moore algorithm". Digraphs: Theory, Algorithms and Applications (First ed.). ISBN 978-1-84800-997-4.
- 2. Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). "Chapter 6: Graph Algorithms". Algorithms in a Nutshell. O'Reilly Media. pp. 160–164. ISBN 978-0-596-51624-6.