經典算法研究：SPFA 算法求解最短路徑——浙大復試真題實戰

作者：July、sunbaigui | 日期：2011年3月25日

前言：學習算法的幾點建議

1. 找到感興趣分支深入鑽研
2. 興趣驅動，拒絕浮躁
3. 建立題目→數據結構→算法的直覺映射
4. 多刷題（ACM、POJ、面試題、復試機試）
5. 重實踐、重思考、重優化
6. 數據結構是基石，通曉一個數據結構 = 通曉一大片算法
7. 重優化，重原理機制而非單純調用

浙大 2010 復試機試真題：最短路徑問題

問題描述

• n 個點（1~n），m 條無向邊
• 每條邊有長度 d 和花費 p
• 給定起點 s、終點 t
• 輸出最短距離及其花費；最短距離多條時輸出花費最小者
• 輸入以 n=m=0 結束
• 約束：1 < n ≤ 1000, 0 < m < 100000, s ≠ t

主流最短路算法比較

SPFA 算法優勢

• Bellman-Ford 隊列優化版，由西南交通大學段凡丁 1994 年發表
• 解決 Dijkstra 不支持負權邊的缺陷
• 平均每個頂點入隊 ≤ 2 次，期望時間 O(E)，實際遠快於堆優化 Dijkstra
• 無向圖 APSP（全源最短路）優化後效率極高

SPFA 算法原理詳解

核心思想：動態逼近 + 隊列優化

• 維護距離估計數組 d[]
• 先進先出隊列保存待優化頂點
• 取隊首 u，用其當前最短距離對出邊 (u,v) 進行松弛
• 若 v 距離更新且不在隊列中，入隊
• 重複直到隊列為空

偽代碼

SPFA(G, w, s):
    INITIALIZE-SINGLE-SOURCE(G, s)
    Q ← ∅
    for each v ∈ V[G]: q[v] = 0
    ENQUEUE(Q, s); q[s] = 1
    
    while Q ≠ ∅:
        u ← DEQUEUE(Q); q[u] = 0
        for each edge (u,v) ∈ E[G]:
            t ← d[v]
            RELAX(u, v, w)
            π[v] ← u
            if d[v] < t and q[v] == 0:
                ENQUEUE(Q, v); q[v] = 1

關鍵性質

• 若最短路存在，必能求出最小值
• 期望時間 O(kE)，k 為平均入隊次數，通常 k ≤ 2
• 最好情況 O(E)（退化為 BFS），最壞 O(VE)（退化為 Bellman-Ford）
• 隨機圖平均性能極優

真題求解：雙權重最短路（距離優先、花費次之）

數據結構設計

struct Node {
    int to, dist, cost;  // 目標點、長度、花費
};
vector graph[1005];
int d[1005][2];          // d[i][0]=最短距離, d[i][1]=對應最小花費
bool inQueue[1005];

SPFA 核心邏輯

void spfa(int s) {
    for (int i = 1; i <= N; i++) d[i][0] = d[i][1] = INF;
    d[s][0] = d[s][1] = 0;
    
    queue q;
    q.push(s); inQueue[s] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        
        for (auto& e : graph[u]) {
            int v = e.to;
            int nd = d[u][0] + e.dist;
            int nc = d[u][1] + e.cost;
            
            // 距離更短，或距離相等但花費更小
            if (nd < d[v][0] || (nd == d[v][0] && nc < d[v][1])) {
                d[v][0] = nd;
                d[v][1] = nc;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
}

完整流程

1. 讀入 n, m，構建鄰接表（無向邊雙向添加）
2. 讀入 s, t
3. 調用 spfa(s)
4. 輸出 d[t][0] 和 d[t][1]
5. 循環處理多組測試數據直到 n=m=0

總結

SPFA 以隊列優化 Bellman-Ford，兼具負權支持與高效能，是解決單源最短路（含雙權重變體）的實戰首選。浙大真題通過雙維距離數組優雅處理「距離優先、花費次之」的多目標優化需求。掌握 SPFA 核心邏輯與變體擴展，是算法競賽與工程實戰的必備技能。