初步了解

Bellman-Ford算法是一種用于尋找帶有負權邊的圖中的單源最短路徑的算法。它可以處理一般的圖，包括存在負權邊和負權環的情況。

以下是Bellman-Ford算法的基本思想和步驟：

• 初始化：將源節點的距離設置為0，將所有其他節點的距離設置為無窮大（或一個很大的數）。

• 進行松弛操作：對圖中的每條邊進行一輪松弛操作。松弛操作是指通過檢查是否存在一條更短路徑來更新節點的距離值。

• 重復進行步驟2：重復進行|V|-1次松弛操作，其中|V|是圖中節點的數量。這是為了確保所有可能的最短路徑都被考慮到。

• 檢測負權環：如果在進行第|V|-1次松弛操作后，仍然存在可以被進一步松弛的邊，那么說明圖中存在負權環。在這種情況下，Bellman-Ford算法無法得出正確的最短路徑。

• 輸出結果：如果不存在負權環，則最終的距離值就是源節點到每個節點的最短路徑長度。

Bellman-Ford算法的時間復雜度為O(|V| * |E|)，其中|V|是節點數，|E|是邊數。它可以處理負權邊，但是在圖中存在負權環的情況下，算法將無法收斂。

負權環是指在圖中存在一個環路，其中環路上的邊的權重之和為負值。換句話說，如果從起點沿著環路走一圈回到起點，所經過的邊的權重之和是負數。
在最短路徑算法中，負權環是一個問題，因為它會導致無限循環的情況。當存在負權環時，最短路徑就沒有意義，因為可以通過無限次地繞著負權環來獲得更小的路徑長度。
猜想一下，如果一個回路下來權值是一個負值，那么多繞幾圈權值越來越小，這樣就不存在最短路徑

注意了解為什么經過|V| - 1 次操作后仍然可以被進一步松弛的邊那么說明圖中存在負權環？
在一個沒有負權環的圖中，最短路徑的長度最多包含|V|-1條邊。而當存在負權環時，路徑可以無限地繞著負權環循環，從而使路徑的長度無限減小。

正式了解

我們來看看代碼實現

#include <iostream>
#include <vector>
#include <limits>struct Edge {int source;int destination;int weight;
};void BellmanFord(const std::vector<Edge>& edges, int numVertices, int source) {std::vector<int> distance(numVertices, std::numeric_limits<int>::max());std::vector<int> predecessor(numVertices, -1);distance[source] = 0;// 進行|V|-1次松弛操作for (int i = 1; i <= numVertices - 1; ++i) {for (const auto& edge : edges) {if (distance[edge.source] != std::numeric_limits<int>::max() &&distance[edge.source] + edge.weight < distance[edge.destination]) {distance[edge.destination] = distance[edge.source] + edge.weight;predecessor[edge.destination] = edge.source;}}}// 檢測負權環for (const auto& edge : edges) {if (distance[edge.source] != std::numeric_limits<int>::max() &&distance[edge.source] + edge.weight < distance[edge.destination]) {std::cout << "圖中存在負權環" << std::endl;return;}}// 輸出最短路徑std::cout << "節點\t距離\t路徑" << std::endl;for (int i = 0; i < numVertices; ++i) {std::cout << i << "\t" << distance[i] << "\t";std::vector<int> path;int current = i;while (current != source) {path.push_back(current);current = predecessor[current];}path.push_back(source);for (int j = path.size() - 1; j >= 0; --j) {std::cout << path[j] << " ";}std::cout << std::endl;}
}int main() {int numVertices = 5;std::vector<Edge> edges = {{0, 1, -1},{0, 2, 4},{1, 2, 3},{1, 3, 2},{1, 4, 2},{3, 2, 5},{3, 1, 1},{4, 3, -3}};int source = 0;BellmanFord(edges, numVertices, source);return 0;
}

代碼還是比較好理解的

當實現 Bellman-Ford 算法時，我們的目標是計算從給定源節點到圖中所有其他節點的最短路徑。下面是代碼實現的總體思路：

定義一個結構體 Edge 來表示圖的邊。它包含三個屬性：源節點 source、目標節點 destination 和邊的權重 weight。

BellmanFord 函數接受邊的列表 edges、節點數量 numVertices 和源節點 source 作為輸入參數。

初始化兩個數組：distance 和 predecessor，分別用于存儲從源節點到每個節點的距離和前驅節點。

將 distance 數組中除了源節點之外的所有元素初始化為無窮大，表示初始狀態下到達這些節點的距離都是無窮大。將 predecessor 數組中所有元素初始化為 -1，表示初始狀態下這些節點沒有前驅節點。

進行 numVertices - 1 次松弛操作。每次循環遍歷邊的列表，對每條邊進行松弛操作。如果發現從源節點出發經過當前邊到達目標節點的路徑比已知的最短路徑更短，則更新 distance 數組和 predecessor 數組。

完成 numVertices - 1 次松弛操作后，檢查是否存在負權環。遍歷邊的列表，再次進行一次松弛操作。如果發現存在從源節點出發經過當前邊到達目標節點的路徑比已知的最短路徑更短，則說明圖中存在負權環。

最后，輸出最短路徑的結果。遍歷每個節點，打印節點的索引、從源節點到該節點的最短距離以及完整的最短路徑。使用 predecessor 數組回溯每個節點的前驅節點，構建完整的路徑。

這個實現思路遵循了 Bellman-Ford 算法的基本步驟，首先進行多次松弛操作以計算最短路徑，然后檢測負權環來判斷是否存在無限縮小路徑的可能性。最后，通過回溯前驅節點來構建最短路徑。