您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

圖論最短路徑演算法全解析：Floyd-Warshall、Dijkstra、Bellman-Ford 與隊列優化 (SPFA) 完整實作

編輯：關於C++

最短路徑是圖論核心問題，分為多源 (任意兩點) 與單源 (固定起點) 兩大類。本文系統講解四大經典演算法：Floyd-Warshall (多源、動態規劃)、Dijkstra (單源、貪心+堆優化)、Bellman-Ford (單源、負權邊支援)、SPFA (Bellman-Ford 隊列優化)，含核心邏輯、完整 C++ 實作、時間/空間複雜度、適用場景與對比選型指南。

一、Floyd-Warshall：多源最短路徑 (動態規劃)

核心思想

狀態 dp[k][i][j]：只允許經過編號 1..k 的頂點作中轉時，i→j 的最短路徑。遞推：

for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (dist[i][j] > dist[i][k] + dist[k][j])
                dist[i][j] = dist[i][k] + dist[k][j];

空間優化：dist 直接原地更新 (滾動陣列)，因 k 較小的值不會被較大的 k 依賴。

完整實作

#include <bits/stdc++.h>
using namespace std;
const long long INF = 4e18;
int main() {
    int n = 4, m = 8;
    vector> dist(n, vector(n, INF));
    for (int i = 0; i < n; ++i) dist[i][i] = 0;
    // 邊: u v w
    vector> edges = {
        {0,1,2}, {0,2,6}, {0,3,4}, {1,2,3},
        {2,0,7}, {2,3,1}, {3,0,5}, {3,2,12}
    };
    for (auto [u,v,w] : edges) dist[u][v] = w;

    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            if (dist[i][k] < INF)
                for (int j = 0; j < n; ++j)
                    if (dist[k][j] < INF && dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];

    // 負環檢測：對角線 < 0
    for (int i = 0; i < n; ++i) if (dist[i][i] < 0) cout << "Negative cycle!\n";

    for (auto& row : dist) {
        for (auto d : row) cout << (d==INF? "INF" : to_string(d)) << ' ';
        cout << '\n';
    }
}

特性總結

時間 O(N³)，空間 O(N²)。
**支援負權邊**，**可檢測負環** (對角線 < 0)。
程式碼極短，適合 N ≤ 400、稠密圖、需所有點對最短路徑場景。
無法輸出具體路徑 (需額外 path 陣列記錄中轉點)。

二、Dijkstra：單源最短路徑 (貪心 + 優先隊列)

核心思想

維護集合 S (已確定最短路徑頂點) 與 dist[] (源點到各點當前最短估計)。每次從 V-S 中取 dist 最小頂點 u 加入 S，對 u 的出邊進行**鬆弛**。

堆優化版實作 (O((M+N)logN))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
int main() {
    int n = 6, m = 9;
    vector>> adj(n);
    // u v w
    vector> edges = {
        {0,1,1}, {0,2,12}, {1,2,9}, {1,3,3},
        {2,4,5}, {3,2,4}, {3,4,13}, {3,5,15}, {4,5,4}
    };
    for (auto [u,v,w] : edges) adj[u].push_back({v,w});

    int s = 0;
    vector dist(n, INF);
    dist[s] = 0;
    priority_queue, vector>, greater>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue; // 延遲刪除
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (ll d : dist) cout << (d==INF? -1 : d) << ' ';
}

關鍵限制與優化

**不支援負權邊** (貪心性質失效)。
稠密圖 M ≈ N² 時 O(N²) 矩陣版更優 (無堆開銷)。
可擴展性極強：第二短路徑、K 短路徑、狀態空間圖 (如帶限制條件) 均可改造。

三、Bellman-Ford：單源負權邊通解

核心思想

對**所有邊**進行 N-1 輪鬆弛。第 k 輪結束後，dist[v] 為源點經**最多 k 條邊**到達 v 的最短路徑。最短路徑不含環 → 至多 N-1 條邊。

完整實作與負環檢測

struct Edge { int u, v, w; };
int main() {
    int n = 5, m = 5;
    vector edges = {{1,2,2}, {0,1,-3}, {0,4,5}, {3,4,2}, {2,3,3}};
    const ll INF = 4e18;
    vector dist(n, INF);
    dist[0] = 0;

    for (int k = 1; k <= n-1; ++k) {
        bool updated = false;
        for (auto& e : edges) {
            if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break; // 提前收斂優化
    }

    // 負環檢測：第 N 輪仍能鬆弛
    bool hasNegCycle = false;
    for (auto& e : edges)
        if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w)
            hasNegCycle = true;
    cout << (hasNegCycle ? "Negative Cycle" : "No Negative Cycle") << '\n';
}

特性

時間 O(NM)，空間 O(M) (邊表)。
**完美支援負權邊**，**可檢測負環**。
適用稀疏圖、需負權邊場景 (如差分約束系統、套利檢測)。

四、SPFA (Queue-Optimized Bellman-Ford)

核心優化

只有**上一輪鬆弛成功**的頂點，才可能引起鄰接點更新。維護隊列 q 存放待鬆弛頂點，inqueue[] 去重，count[] 記錄入隊次數判斷負環 (count[v] > N)。

完整實作

#include <bits/stdc++.h>
using namespace std;
struct Edge { int to, w; };
int main() {
    int n = 5, m = 7;
    vector> adj(n);
    // u v w
    vector> edges = {
        {0,1,2}, {0,4,10}, {1,2,3}, {1,4,7},
        {2,3,4}, {3,4,5}, {4,2,6}
    };
    for (auto [u,v,w] : edges) adj[u].push_back({v,w});

    const ll INF = 4e18;
    vector dist(n, INF);
    vector inq(n, false);
    vector cnt(n, 0);
    queue q;
    int s = 0;
    dist[s] = 0; q.push(s); inq[s] = true; cnt[s] = 1;

    bool negCycle = false;
    while (!q.empty() && !negCycle) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    if (++cnt[v] > n) { negCycle = true; break; }
                }
            }
        }
    }
    if (negCycle) cout << "Negative Cycle\n";
    else for (ll d : dist) cout << (d==INF? -1 : d) << ' ';
}

特性

平均效能遠優於 Bellman-Ford，最壞仍 O(NM) (構造特定圖可退化)。
負環判斷：count[v] > N (某點入隊超過 N 次)。
形式類 BFS，但頂點可多次入隊 (距離更新即重新入隊)。

五、四大演算法對比選型指南

演算法	問題類型	時間複雜度	空間	負權邊	負環檢測	適用場景
Floyd-Warshall	多源 (全點對)	O(N³)	O(N²)	✅	✅ (對角線)	N≤400、稠密圖、需所有點對距離、程式碼簡短優先
Dijkstra (Heap)	單源	O((M+N)logN)	O(M+N)	❌	❌	非負權、大規模稀疏圖、可擴展性需求 (K短路、狀態圖)
Bellman-Ford	單源	O(NM)	O(M)	✅	✅	負權邊、稀疏圖、差分約束、教學驗證
SPFA	單源	平均 O(kM), 最壞 O(NM)	O(M+N)	✅	✅ (入隊次數)	負權邊實戰首選、隨機圖極快、競程常用

六、進階選型決策樹

需**所有點對**最短路徑 → Floyd (N 小) 或 N 次 Dijkstra (N 大、非負權)。
單源 + **非負權** → Dijkstra + Heap (通用首選)。
單源 + **負權邊** → SPFA (實戰首選) / Bellman-Ford (嚴格證明/教學)。
**差分約束系統** (不等式組 x_j - x_i ≤ c) → 建圖跑 Bellman-Ford/SPFA 判斷可行性 (負環 = 無解)。
**第二短路徑 / K 短路徑 / 帶狀態限制** → 擴展 Dijkstra 狀態空間。

七、歷史小檔案

Floyd-Warshall：Robert Floyd (1962, ACM) / Stephen Warshall (1962, 獨立發表)。Floyd 亦共同發明堆排序 (1964, 與 J.W.J. Williams)，1978 圖靈獎得主。
Dijkstra：Edsger W. Dijkstra (1956 發現, 1959 發表於 Numerische Mathematik 創刊號)。
Bellman-Ford：Richard Bellman (1958) / Lester Ford Jr. (1956) / Edward F. Moore (1957, BFS 發明者) → 又稱 Bellman-Ford-Moore。

掌握四大演算法的原理邊界與工程實作細節，是解決圖論最短路徑問題、通過競程考試、設計路由/物流/網路優化系統的核心武庫。