【數據結構與算法】圖 Floyd算法

相關題目：?

1334. 閾值距離內鄰居最少的城市 - 力扣（LeetCode）

資料：?

Floyd算法原理及公式推導 - 知乎

Floyd 算法是一種經典的動態規劃算法，用與求解圖中所有頂點之間的最短短路路徑。它由Robert Floyd? 于1962 年提出，核心思想是通過“中間頂點”逐步松弛路徑長度，最終得到任意兩點間的最短距離。

算法核心：?

圖的類型：無向圖，有向圖（注意邊的方向性）

邊權特性： 支持負權邊，但是不允許“包含負權邊的回路”，否則會導致路徑長度無線減小，無法收斂。

圖的存儲：??

使用鄰接矩陣存儲，用于快速訪問任意兩點間的邊權。

算法原理步驟

動態規劃狀態定義??

定義 dp[k][i][j]=表示只允許使用前k個節點作為中間節點，頂點 i 到頂點j 的最短距離。

根據狀態轉移：?

不選擇第k個節點作為中間節點:

$dp[k][i][j]=dp[k-1][i][j]$

選擇第k個頂點組委中間節點：路徑拆分為i->k->j

$dp[k][i][j] =dp[k-1][i][j]+dp[k-1][i][j]$ .

狀態轉移方程為：

$dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])$

空間優化（關鍵）

觀察dp[k][...]? ?僅依賴dp[k-1][...]? ，因此無需存儲所有k 層狀態，可以直接用二維數組dist覆蓋更新

（k 作為外層循環，每次更新dist[i]j[ 時復用之前的結果]）。

實現步驟

假設? 圖中有n個頂點，鄰接矩陣初始化為dist ，步驟如下：?

初始化鄰接矩陣

對頂點i, dist[i][i]=0? 自身到自身的距離為0?

如果頂點i和j 直接有直接的邊，權重為w 則dist[i][j]=w

如果頂點i 和j 無直接邊， $dist[i][j]=\infty$ ?，表示不可達，通常用一個極大值如10^9

外層循環（枚舉中間節點k）

遍歷所有可能的中間頂點k(從1到n)

中間循環：枚舉起點i:

?遍歷所有可能的起點i (從1到n)

內側循環：枚舉終點 j

遍歷所有可能的終點j , （1到 n ）,執行松弛操作，

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])$

（可選）檢測負權回路：

算法結束后，若存在? $(dist[i][i] < 0)$ ，則說明圖中存在包含頂點?i?的負權回路（因為自身到自身的距離不可能為負）

代碼?

c++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;const int INF = INT_MAX / 2;  // 避免加法溢出int main() {int n, m;  // n: 頂點數, m: 邊數cin >> n >> m;// 1. 初始化鄰接矩陣vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));for (int i = 1; i <= n; ++i) {dist[i][i] = 0;  // 自身到自身距離為0}// 讀入邊：u -> v，權值 wfor (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;dist[u][v] = w;  // 若為無向圖，需額外添加 dist[v][u] = w}// 2. Floyd 算法核心（k: 中間頂點，i: 起點，j: 終點）for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {// 若 i->k 或 k->j 不可達，則跳過（避免 INF + INF 溢出）if (dist[i][k] != INF && dist[k][j] != INF) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}}// 3. 輸出所有頂點間的最短距離cout << "所有頂點間的最短距離：" << endl;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (dist[i][j] == INF) {cout << "INF ";  // 不可達} else {cout << dist[i][j] << " ";}}cout << endl;}// 4. 檢測負權回路bool has_negative_cycle = false;for (int i = 1; i <= n; ++i) {if (dist[i][i] < 0) {has_negative_cycle = true;break;}}if (has_negative_cycle) {cout << "圖中存在負權回路！" << endl;}return 0;
}

python?

import sys
# 避免類似 C++ 中 INT_MAX 溢出問題，使用一個足夠大的數表示“不可達”
INF = float('inf')def main():# 讀取輸入（頂點數 n，邊數 m）# 注：Python 中 input() 讀取單行，需拆分字符串獲取整數；若輸入較大可改用 sys.stdin 提速n, m = map(int, sys.stdin.readline().split())# 1. 初始化鄰接矩陣：dist[i][j] 表示頂點 i 到 j 的初始距離# 頂點編號從 1 開始（與 C++ 保持一致，避免索引偏移）dist = [[INF] * (n + 1) for _ in range(n + 1)]# 自身到自身的距離為 0for i in range(1, n + 1):dist[i][i] = 0# 讀入 m 條邊：u -> v，權值 w（有向邊）for _ in range(m):u, v, w = map(int, sys.stdin.readline().split())# 若存在多條從 u 到 v 的邊，保留權值最小的一條（與原 C++ 邏輯一致）dist[u][v] = w# 【若為無向圖】需添加以下一行（無向邊等價于雙向有向邊）：# dist[v][u] = w# 2. Floyd 算法核心：三層循環枚舉中間頂點、起點、終點# k：中間頂點（允許經過前 k 個頂點時更新最短路徑）for k in range(1, n + 1):# i：路徑起點for i in range(1, n + 1):# j：路徑終點for j in range(1, n + 1):# 跳過不可達的情況（避免 INF + INF 無意義計算）if dist[i][k] != INF and dist[k][j] != INF:# 松弛操作：更新 i->j 的最短距離if dist[i][j] > dist[i][k] + dist[k][j]:dist[i][j] = dist[i][k] + dist[k][j]# 3. 輸出所有頂點間的最短距離（格式與 C++ 一致）print("所有頂點間的最短距離：")for i in range(1, n + 1):row = []for j in range(1, n + 1):if dist[i][j] == INF:row.append("INF")else:row.append(str(dist[i][j]))# 用空格連接一行的元素，與 C++ 輸出格式對齊print(' '.join(row))# 4. 檢測負權回路：若存在頂點 i 滿足 dist[i][i] < 0，說明有負權回路has_negative_cycle = Falsefor i in range(1, n + 1):if dist[i][i] < 0:has_negative_cycle = Truebreakif has_negative_cycle:print("圖中存在負權回路！")if __name__ == "__main__":main()

不可達值（INF）： Python 中用 float('inf') 表示 “無窮大”，比 C++ 的 INT_MAX/2 更直觀，且天然避免整數溢出問題（無需擔心 INF + INF 超出范圍）。

鄰接矩陣初始化：用 Python 列表推導式 [[INF]*(n+1) for _ in range(n+1)] 創建 (n+1)×(n+1) 的矩陣（頂點編號從 1 開始，與 C++ 一致，減少邏輯偏移）。

輸入處理： 使用 sys.stdin.readline() 替代 input()，處理大量輸入時效率更高（適配題目中可能的大規模圖數據）；通過 map(int, ...split()) 拆分輸入字符串為整數，與 C++ 的 cin >> 邏輯一致。核心松弛操作：保留三層循環的順序（k→i→j），僅將 C++ 的 min() 函數替換為 Python 的條件判斷（if dist[i][j] > ...），邏輯完全等價，且更符合 Python 代碼習慣。

輸出格式： 用列表 row 收集每行的輸出內容，最后通過 ' '.join(row) 用空格連接，確保輸出格式與 C++ 一致（如 “INF” 對應不可達，數字對應最短距離）。負權回路檢測：保留原邏輯 —— 遍歷所有頂點 i，若 dist[i][i] < 0，說明存在經過 i 的負權回路（因為 “自身到自身的最短路徑” 不可能為負）。

示例?

示例1

輸入（3 個頂點，4 條有向邊）：

plaintext

輸出：

所有頂點間的最短距離： 0 2 3 -3 0 1 -4 -2 0 圖中存在負權回路！

該示例中，dist[1][1] = 0、dist[2][2] = 0、dist[3][3] = 0 看似無負，但實際計算過程中會發現循環 1→2→3→1 的總權值為 2+1+(-4) = -1 < 0，最終代碼會正確檢測出負權回路。

示例2

無負權邊的有向圖示例

中間頂點如何優化最短路徑

示例場景：4 個頂點的有向圖

假設我們有一個包含 4 個頂點（編號 1~4）的有向圖，邊的連接和權值如下（邊的方向和權重是核心）：

1 → 2，權值 3
1 → 3，權值 6
2 → 3，權值 2
2 → 4，權值 5
3 → 4，權值 1
4 沒有出邊

第一步：明確輸入格式

根據代碼的輸入要求（先輸入頂點數?n?和邊數?m，再輸入?m?條邊的起點、終點、權值），該示例的輸入如下：

plaintext

第二步：算法執行邏輯拆解（核心步驟）

我們會按 Floyd 算法的三層循環（中間頂點?k?→ 起點?i?→ 終點?j），逐步展示鄰接矩陣?dist?的更新過程，理解 “中間頂點如何縮短路徑”。

1. 初始化鄰接矩陣

初始時，dist[i][j]?的規則：

自身到自身：dist[i][i] = 0
有直接邊：dist[i][j] = 邊權
無直接邊：dist[i][j] = INF（用?∞?表示）

初始?dist?矩陣（行是起點，列是終點）：

起點 \ 終點	1	2	3	4
1	0	3	6	∞
2	∞	0	2	5
3	∞	∞	0	1
4	∞	∞	∞	0

2. 枚舉中間頂點 k=1（允許經過頂點 1 優化路徑）

此時檢查所有 i→j，看是否能通過 i→1→j 縮短路徑。由于頂點 1 的出邊只有 1→2、1→3，且大部分 i→1 不可達（如 i=2,3,4 到 1 是 ∞），因此矩陣無更新。

3. 枚舉中間頂點?`k=2`（允許經過頂點 2 優化路徑）

檢查所有?i→j，看是否能通過?i→2→j?縮短路徑，關鍵更新如下：

對于?i=1, j=3：原路徑 1→3 權值 6；新路徑 1→2→3 權值?3+2=5?→ 更新?dist[1][3] = 5
對于?i=1, j=4：原路徑 1→4 是?∞；新路徑 1→2→4 權值?3+5=8?→ 更新?dist[1][4] = 8

更新后的?dist?矩陣：

起點 \ 終點	1	2	3	4
1	0	3	5	8
2	∞	0	2	5
3	∞	∞	0	1
4	∞	∞	∞	0

4. 枚舉中間頂點?`k=3`（允許經過頂點 3 優化路徑）

檢查所有?i→j，看是否能通過?i→3→j?縮短路徑，關鍵更新如下：

對于?i=1, j=4：原路徑 1→4 權值 8；新路徑 1→3→4 權值?5+1=6?→ 更新?dist[1][4] = 6
對于?i=2, j=4：原路徑 2→4 權值 5；新路徑 2→3→4 權值?2+1=3?→ 更新?dist[2][4] = 3

更新后的?dist?矩陣：

起點 \ 終點	1	2	3	4
1	0	3	5	6
2	∞	0	2	3
3	∞	∞	0	1
4	∞	∞	∞	0

5. 枚舉中間頂點?`k=4`（允許經過頂點 4 優化路徑）

由于頂點 4 沒有出邊（所有?4→j?除了自身都是?∞），因此矩陣無更新。

第三步：代碼輸出結果

將上述輸入代入 Python 代碼，最終輸出如下（包含所有頂點間的最短距離，且無負權回路）：

plaintext

所有頂點間的最短距離：
0 3 5 6
INF 0 2 3
INF INF 0 1
INF INF INF 0

結果解讀

輸出矩陣的每一行代表 “從當前起點到所有終點的最短距離”：

起點 1 到各終點：1→1（0）、1→2（3）、1→3（5，1→2→3）、1→4（6，1→2→3→4）
起點 2 到各終點：2→1（不可達）、2→2（0）、2→3（2）、2→4（3，2→3→4）
起點 3 到各終點：3→1/2（不可達）、3→3（0）、3→4（1）
起點 4 到各終點：4→1/2/3（不可達）、4→4（0）

這與我們手動拆解的 “最優路徑” 完全一致，驗證了代碼的正確性。

額外測試：含負權邊（無負權回路）若在上述示例中添加一條邊 3→1，權值 -2（無負權回路），輸入變為： plaintext 4 6 1 2 3 1 3 6 2 3 2 2 4 5 3 4 1 3 1 -2 代碼會檢測到 “無負權回路”，且更新后的 dist[2][1] 會變為 2→3→1 的權值 2 + (-2) = 0，dist[3][1] = -2 等，進一步體現 Floyd 算法對負權邊的支持。