多源最短路簡介

多源最短路算法用于解決圖中任意兩節點間最短路徑的問題，廣泛應用于交通網絡、社交關系分析、路由優化等場景。與單源最短路（如Dijkstra）不同，它一次性計算所有節點對的最短距離，適合需要全局路徑規劃的場景。

核心算法

Floyd算法：基于動態規劃，通過三重循環松弛所有中間節點，時間復雜度為 $O(V^3)$，適合稠密圖或需要處理負權邊的場景。其空間復雜度為 $O(V^2)$，需存儲所有節點對的距離矩陣。

Floyd算法：

Floyd算法本質是用動態規劃，來求任意兩個節點之間的最短路，也成為插點法。通過不斷在兩結點之間加入新的點，來更新最短路。且適用于任何圖，不管有向無向，邊權正負，但必須有最短路存在（也就是不存在負環）。
其實最本質上，就是分階段，逐步更新出最終結果。
算法流程：

1. 狀態表示：f[k][i][j] 表示，僅僅通過 [1,k] 這些點，計算出結點 i 走到結點 j 的最短路徑長度
2. 狀態轉移方程：不選新來的點：f[k][i][j] = f[k-1][i][j] 選擇新來的點：f[k][i][j] = f[k-1][i][k] + f[k-1][k][j]
3. 空間優化：只會用到上一層的狀態，因此可以優化掉第一維。f[i][j]為初始狀態下i到j的距離，如果沒有邊則為無窮
4. 初始化：f[i][j] = 0
5. 填表順序：一定要先枚舉 k 再枚舉 i 和 j。因為外面填表的時候需要依賴 k-1 曾的狀態，因此，必須先枚舉 k。

代碼實現：

int main()
{cin >> n >> m;memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++)f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;f[a][b] = f[b][a] = min(f[a][b], c);}//floydfor (int k = 1; k <= n; k++)//以那個點作為新的中間的橋梁節點（之前的點已經用過并保存在數組中，因此，k = n時使用的橋梁節點是前n個所有結點）{for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}}}for (int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)cout << f[i][j] << " ";cout << endl;}
}