Bellman-Ford演算法 求有邊數限制的最短路
- 2022 年 3 月 21 日
- 筆記
- Bellman-Ford, 演算法基礎
這個演算法也是緊承我們之前講過的關於圖論的內容，我們在前面分析圖的時候說過了對於不同的圖論問題，我們會有不同的求解方法，那麼這裡我們講到Bellman-Ford演算法是用於解決有邊數限制的求解最短路問題。
我們先介紹一下我們之前講過的Dijkstra演算法為什麼在這裡失靈了，因為我們之前講的Dijkstra演算法是不適合求解含有負權邊的最短路問題，原因如下圖：
換言之，Dijkstra演算法是找距離源點最近的點取更新別的點，這是一種貪心的思想，但是在具有負權邊的問題時，局部最優解不一定是全局最優解，因為存在負權邊，導致一開始大的邊也有可能小下去。
Bellman—Ford演算法的核心：對每一條邊都進行鬆弛操作
每次鬆弛操作實際上是對相鄰節點的訪問(相當於廣度優先搜索)，第n次鬆弛操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過|m| – 1條邊，所以可知Bellman—Ford演算法所得為最短路徑，也可知時間複雜度為O(mn)。
程式碼：
#include<bits/stdc++.h>
#define maxn 510
#define maxm 10010
using namespace std;
int dist[maxn],backup[maxn],n,m,k;
struct EDGE{
int x,y,z;
}edge[maxm];
void bellman_ford(){
memset(dist , 0x3f , sizeof(dist));
dist[1] = 0;
for(int i = 1; i<=k; i++){
memcpy(backup,dist,sizeof(dist));
for(int j = 1; j<=m; j++){
int a = edge[j].x , b = edge[j].y , w = edge[j].z ;
dist[b] = min(dist[b],backup[a] + w);
}
}
}
int main()
{
cin >> n >> m >> k;
for(int i = 1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
edge[i].x = a; edge[i].y = b; edge[i].z = c;
}
bellman_ford();
if(dist[n] > 0x3f3f3f3f/2) cout << “impossible” << ‘\n’;
else cout << dist[n] << ‘\n’;
return 0;
}
分析：
·我們對dist數組還是初始化為0x3f3f3f3f，但是最後在判斷的時候去要求 >=0x3f3f3f3f/2：
這是因為我們在進行鬆弛操作的時候是對每一條邊都進行的， 所以本來時0x3f3f3f3f的地方可能被有負權邊的路徑給更新，所以我們只要保證他在一個量級就行了！
· 我們在每一次更新數值的時候，我們發現用到了一個backup數組，這個是用來幹什麼的呢：
我們在按順序更新數值的時候，我們如果直接用dist數組直接更新，有可能會導致前一個剛被更新的緊接著去更新下一個，這樣就不能保證邊數的限制了！
所以我們就要把上一次的值copy到backup數組中！
