我們之前介紹的兩種最短路徑算法都是單源最短路徑，就是我們要指定一個起點來尋找最短路徑，而我們今天介紹的FloydWarshall算法，可以不指定源點，找到最短路徑：

FloydWarshall算法

在介紹FloydWarshall算法之前，我們先來想一個問題，就是：最短路徑要經過多少頂點呢？
第一種情況他倆之間就是最短距離：

第二種，中間經過了許多結點：

Floyd-Warshall算法是一種在有向圖中尋找所有頂點對之間的最短路徑的算法。它可以在圖中包含負權邊的情況下工作，但是圖中不能包含負權循環。

以下是Floyd-Warshall算法的基本步驟：

1. 初始化：創建一個n×n的距離矩陣D，其中D[i][j]表示從頂點i到頂點j的最短路徑的長度。如果(i,j)之間沒有直接的邊，則D[i][j]設置為無窮大。對于所有的頂點i，D[i][i]=0。

2. 對于每一個中間頂點k，更新距離矩陣D。具體來說，對于每一對頂點(i, j)，如果D[i][j] > D[i][k] + D[k][j]，則更新D[i][j]為D[i][k] + D[k][j]。這相當于檢查是否可以通過k作為中間頂點來獲得從i到j的更短路徑。

3. 重復步驟2，直到所有可能的中間頂點都被考慮過。

4. 最后，距離矩陣D中的每個元素D[i][j]將包含從頂點i到頂點j的最短路徑的長度。

void FloydWarshall(vector<vector<W>>& vvDest, vector<vector<int>>& vvParentpath)
{// 調整vvDest和vvParentpath的大小與頂點數量一致vvDest.resize(_vertex.size());vvParentpath.resize(_vertex.size());// 初始化距離矩陣為最大權重（表示不可達）// 初始化前驅節點矩陣為-1（表示無前驅節點）for (size_t i = 0; i < _vertex.size(); i++){vvDest[i].resize(_vertex.size(), MAX_W);vvParentpath[i].resize(_vertex.size(), -1);}// 初始化距離矩陣和前驅節點矩陣// 如果兩個頂點間存在直接連接，則設置距離矩陣的相應位置為該連接的權重// 并且設置前驅節點為當前頂點for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){// 同一頂點到自身的距離為0，前驅節點為-1if (i == j){vvDest[i][j] = 0;vvParentpath[i][j] = -1;}// 如果兩頂點之間有直接連接，并且權重不是最大權重（即可達）if (_matrix[i][j] != MAX_W){vvDest[i][j] = _matrix[i][j];vvParentpath[i][j] = i;}else{// 如果兩頂點之間不可達，前驅節點為-1vvParentpath[i][j] = -1;}}}// 這里是核心部分，遍歷所有頂點作為中間頂點，以檢查是否存在更短路徑for (size_t k = 0; k < _vertex.size(); k++){for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){// 如果存在通過頂點k作為中間頂點的更短路徑，則更新距離和前驅節點if (vvDest[i][k] != MAX_W && vvDest[k][j] != MAX_W && vvDest[i][k] + vvDest[k][j] < vvDest[i][j]){vvDest[i][j] = vvDest[i][k] + vvDest[k][j];vvParentpath[i][j] = vvParentpath[k][j];}}}// 打印每次迭代后的距離矩陣和前驅節點矩陣（可選）//打印權值和路徑矩陣觀察數據//cout << "     ";//for (size_t i = 0; i < _vertex.size(); i++)//{//	cout << _vertex[i] << " ";//}//cout << endl;for (size_t i = 0; i < _vertex.size(); ++i){cout << _vertex[i] << " ";for (size_t j = 0; j < _vertex.size(); ++j){if (vvDest[i][j] == MAX_W){//cout << "*" << " ";printf("%3c", '*');}else{//cout << vvDest[i][j] << " ";printf("%3d", vvDest[i][j]);}}cout << endl;}cout << endl;for (size_t i = 0; i < _vertex.size(); ++i){for (size_t j = 0; j < _vertex.size(); ++j){//cout << vvParentPath[i][j] << " ";printf("%3d", vvParentpath[i][j]);}cout << endl;}cout << "=================================" << endl;}}
}

我們構建這樣的圖：

	void TestFloydWarshall(){const char* str = "12345";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('1', '2', 3);g.AddEdge('1', '3', 8);g.AddEdge('1', '5', -4);g.AddEdge('2', '4', 1);g.AddEdge('2', '5', 7);g.AddEdge('3', '2', 4);g.AddEdge('4', '1', 2);g.AddEdge('4', '3', -5);g.AddEdge('5', '4', 6);vector<vector<int>> vvDist;vector<vector<int>> vvParentPath;g.FloydWarshall(vvDist, vvParentPath);}

大家可以對應一下上面的圖，這里注意一下，我們的路徑的數組存儲的是下標，所以每組的第二個圖比上圖中的數值小1，這是正常的。

我們可以把每個結點到其他結點的最短路徑打印出來：

	void TestFloydWarshall(){const char* str = "12345";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('1', '2', 3);g.AddEdge('1', '3', 8);g.AddEdge('1', '5', -4);g.AddEdge('2', '4', 1);g.AddEdge('2', '5', 7);g.AddEdge('3', '2', 4);g.AddEdge('4', '1', 2);g.AddEdge('4', '3', -5);g.AddEdge('5', '4', 6);vector<vector<int>> vvDist;vector<vector<int>> vvParentPath;g.FloydWarshall(vvDist, vvParentPath);// 打印任意兩點之間的最短路徑for (size_t i = 0; i < strlen(str); ++i){g.PrintShortestPath(str[i], vvDist[i], vvParentPath[i]);cout << endl;}}

我們也可以把之前小潮的圖拿出來測測：

三種最短路徑算法比較

在圖論中，尋找最短路徑是常見的問題，有多種算法可以解決這個問題，包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。下面是對這三種算法的比較：

1. Dijkstra算法

適用場景：適用于沒有負權邊的加權圖，無論是有向還是無向圖。

優點：

• 時間復雜度較低，使用優先隊列優化后的時間復雜度為O((V+E)logV)。
• 算法簡單，易于理解和實現。

缺點：

• 不能處理含有負權邊的圖。

2. Bellman-Ford算法

適用場景：適用于任何加權圖，包括含有負權邊的圖，但不能有負權回路。

優點：

• 可以檢測并報告圖中是否存在負權回路。
• 對于稀疏圖，性能優于Floyd-Warshall算法。

缺點：

• 時間復雜度較高，為O(VE)，當E較大時效率低。
• 每次迭代都需要更新所有邊，即使某些邊的最短路徑已經確定。

3. Floyd-Warshall算法

適用場景：適用于任何加權圖，包括含有負權邊的圖，但不能有負權回路。特別適合于求解所有頂點對之間的最短路徑問題。

優點：

• 可以一次計算出所有頂點對的最短路徑。
• 算法簡潔，易于理解。

缺點：

• 時間復雜度高，為O(V^3)，對于大規模圖的計算效率低下。
• 需要額外的空間來存儲中間結果，空間復雜度為O(V^2)。

總結

• 如果只需要求解單源最短路徑問題，且圖中沒有負權邊，Dijkstra算法是首選。
• 如果圖中可能含有負權邊，但沒有負權回路，Bellman-Ford算法更為適用。
• 當需要求解所有頂點對之間的最短路徑時，Floyd-Warshall算法是最直接的選擇，盡管它的時間和空間復雜度較高。

選擇哪種算法取決于具體的問題背景和圖的特性。