Bellman-Ford的操作步驟

1.初始化距離：將起點的dist值設置為0，其他點的dist值設置為無窮大。

2.執行n-1輪松弛操作：遍歷所有邊，更新最短距離，收斂后可獲得最短路徑。

3.檢測負權環：額外遍歷一次，若還可以進行更新，則說明圖中存在負權環。

Bellman-Ford的代碼實現

#include<iostream>
#include<cstring>
using namespace std;
int n, m;
int dist[105];
int s;
struct edge {int a, b, w;
}e[10005];
void ford() {//可以判斷負邊權回路int x, y, w;int flag = 0;for (int i = 1; i <= n - 1; i++) {//循環到n flag為1 負權環回路flag = 0;for (int j = 0; j < m; j++) {x = e[j].a;y = e[j].b;w = e[j].w;if (dist[x] + w < dist[y]) {dist[y] = dist[x] + w;flag = 1;} }if (flag == 0) {break;}}
}
int main() {cin >> n >> m;for (int i = 0; i < m; i++) {cin >> e[i].a >> e[i].b >> e[i].w;}cin >> s;memset(dist, 0x3f, sizeof(dist));dist[s] = 0;//起點到自己距離為0ford();for (int i = 1; i <= n; i++) {cout << dist[i] << " ";}return 0;
}

Bellman-Ford算法的作用與分析

根據代碼可知，該算法的時間復雜度為O(n*m)，它能用來判斷負權環的存在，同時也能處理負邊權。