簡介

貝爾曼-福特算法（Bellman-Ford Algorithm）是一種用于求解單源最短路徑問題的算法，它可以處理帶有負權邊的圖。 該算法的實現思路是通過不斷迭代松弛操作來更新最短路徑，直到找到最優解。

名詞解釋：
1. 松弛操作：不斷更新最短路徑和前驅結點的操作。
2. 負權回路：繞一圈繞回來發現到自己的距離從0變成了負數，到各結點的距離無限制的降低，停不下來

算法特點

• 貝爾曼-福特算法可以處理帶有負權邊的圖，而迪杰斯特拉算法（Dijkstra's Algorithm）等其他最短路徑算法無法處理這種情況。
• 貝爾曼-福特算法的實現相對簡單，易于理解和編程。
• 貝爾曼-福特算法的時間復雜度為 O(nm)，其中 n 是圖中頂點的個數，m 是圖中邊的個數。 這使得它在稀疏圖中效率較低。

如何理解貝爾曼-福特算法？

想象一下你正在一個城市中尋找最短路徑。 你可以從一個路口開始，沿著道路前進，并記錄下每個路口的距離。 貝爾曼-福特算法的工作方式類似：

• 首先，將所有路口的距離設置為無窮大，并將起點距離設置為 0。

• 然后，遍歷所有道路，并對每個路口進行以下操作：

  • 如果當前路口的距離加上該道路的長度小于該道路終點的距離，則將該道路終點的距離更新為當前路口的距離加上該道路的長度。

• 重復上述步驟 n - 1 次，其中 n 是路口的數量。

通過不斷重復上述步驟，最終可以找到所有路口到起點的最短路徑。

代碼

void ford() {// 初始化距離數組，表示起點到每個頂點的距離為無窮大for (int i = 1; i <= n; i++) {dis[i] = INF;}dis[1] = 0; // 起點到自身的距離為0// 進行n-1次松弛操作for (int k = 1; k <= n - 1; k++) {for (int i = 1; i <= m; i++) {// 如果通過當前邊能夠使終點的距離更短，則更新距離if (dis[v[i]] > dis[u[i]] + w[i]) {dis[v[i]] = dis[u[i]] + w[i];}}}
}

如有不理解的可以上b站上看up主@簡楓葉

總結

Bellman算法的核心就是松馳，沒有貪心策略，也使它的時間復雜度比較高。因為它是單純的松馳。首先我們要明白的是：如果處于第n層的節點，在它上一層的即n-1層所以節點的dist已經確定為最終真實值，那么通過一次遍歷，第n層節點的dist也能被確定為最終真實值。第一次迭代，獲得的信息是：與源點相鄰點的真正dist（第二層節點），（其他點的可能仍為無窮大，或者為松馳一次狀態）；第二次循環，因為第二層的信息已經完全掌握，此次迭代是能確定第三層節點（從源點出發，經過2條邊）的點的真實最短距離。（由于遍歷的過程中，只完全掌握了第一層，其他節點的dist不能完全確定為最終的dist);如此循環，遍歷n-1次，第n層的節點已經遍歷完，至此，所有節點的dist都最終確定了（解釋了為啥能求最短路)

例題P1629 郵遞員送信

?郵遞員送信

?題目描述

有一個郵遞員要送東西，郵局在節點 1。他總共要送 n-1?樣東西，其目的地分別是節點 2?到節點 n。由于這個城市的交通比較繁忙，因此所有的道路都是單行的，共有 m條道路。這個郵遞員每次只能帶一樣東西，并且運送每件物品過后必須返回郵局。求送完這 n-1?樣東西并且最終回到郵局最少需要的時間。

?輸入格式

第一行包括兩個整數，n?和 m，表示城市的節點數量和道路數量。

第二行到第 (m+1)?行，每行三個整數，u,v,w，表示從u?到 v?有一條通過時間為 w?的道路。

?輸出格式

輸出僅一行，包含一個整數，為最少需要的時間。

#include <stdio.h>#define INF 99999999 // 定義無窮大值
#define MAXN 1005 // 最大頂點數
#define MAXM 100005 // 最大邊數int n, m; // 頂點數和邊數
int u[MAXM], v[MAXM], w[MAXM]; // 邊的起點、終點、權值
int dis[MAXN]; // 存儲起點到各頂點的最短距離// 初始化函數，讀入頂點數、邊數以及每條邊的起點、終點、權值
void init() {scanf("%d %d", &n, &m); // 輸入頂點數n和邊數mfor (int i = 1; i <= m; i++) {scanf("%d %d %d", &u[i], &v[i], &w[i]); // 輸入每條邊的起點、終點、權值}
}// 反轉邊的起點和終點
void over() {for (int i = 1; i <= m; i++) {int temp = u[i];u[i] = v[i];v[i] = temp;}
}// Ford算法求解最短路徑
void ford() {// 初始化距離數組，表示起點到每個頂點的距離為無窮大for (int i = 1; i <= n; i++) {dis[i] = INF;}dis[1] = 0; // 起點到自身的距離為0// 進行n-1次松弛操作for (int k = 1; k <= n - 1; k++) {for (int i = 1; i <= m; i++) {// 如果通過當前邊能夠使終點的距離更短，則更新距離if (dis[v[i]] > dis[u[i]] + w[i]) {dis[v[i]] = dis[u[i]] + w[i];}}}
}int main() {init(); // 初始化int ans = 0; // 記錄總距離ford(); // 調用Ford算法計算從起點到各頂點的最短距離for (int i = 1; i <= n; i++) {ans += dis[i]; // 累加起點到各頂點的最短距離}over(); // 反轉邊的起點和終點ford(); // 重新計算最短路徑for (int i = 1; i <= n; i++) {ans += dis[i]; // 累加起點到各頂點的最短距離}printf("%d\n", ans); // 輸出總距離return 0;
}