Shortest Path Faster Algorithm (SPFA)

預備知識

• Graph
• Bellman-Ford Algorithm
• Graph Traversal

Shortest Path Faster Algorithm（簡稱 SPFA）是 Bellman-Ford Algorithm 的一個優化版本，解決的問題完全一樣：求單一起點到其他所有頂點的最短路徑，且允許負權重。差別在於它想辦法跳過大量「不需要做」的鬆弛動作。

白話理解

Bellman-Ford 每一輪都很「死板」：不管上一輪誰的距離有沒有更新，這一輪照樣把所有邊都重新檢查一次，就算某個頂點的距離早就穩定不會再變，還是得陪著大家重新算一次。

SPFA 換了個聰明的做法：只有「距離剛剛被更新過」的頂點，才有可能讓它的鄰居距離也跟著變短，所以只需要重新檢查這些頂點的鄰居就好。 這跟 Graph Traversal 裡 BFS 用 Queue 一層一層往外擴散的精神很像。

解析

SPFA 用一個 Queue 來記錄「接下來需要重新檢查鄰居」的頂點：

1. 初始化：起點距離設為 0，其他頂點設為無限遠，把起點放進 Queue
2. 重複以下動作，直到 Queue 淨空：
   • 從 Queue 取出一個頂點 u
   • 檢查 u 的每一個鄰居 v：如果「經過 u 到 v」比目前記錄的 v 更短，就更新距離
   • 如果 v 的距離被更新了，而且 v 目前不在 Queue 裡，就把 v 放進 Queue（因為 v 變短了，它的鄰居也可能因此跟著變短，需要被重新檢查）
3. Queue 淨空時，所有距離都已經穩定，運算結束

跟 Bellman-Ford 「每輪無腦檢查所有邊」比起來，SPFA 只檢查「真正可能有變化」的那一小群頂點的鄰居，在大部分稀疏圖（邊的數量不多）的情況下，實際跑起來會快上不少。

逐步拆解：用一個小範例走一次流程

沿用 Bellman-Ford 那篇的範例：4 個頂點 A、B、C、D，邊如下（C → A 帶有負權重）：

A --4--> B
A --5--> C
B --3--> D
C --(-2)--> A
C --3--> D

從 A 出發：

步驟	從 Queue 取出	更新內容	Queue 狀態（處理後）
初始化	-	A=0, B=∞, C=∞, D=∞	[A]
1	A	B=0+4=4，C=0+5=5	[B, C]
2	B	D=4+3=7	[C, D]
3	C	D=min(7, 5+3)=7（沒變短，不更新）；A=min(0, 5-2)=0（沒變短，不更新）	[D]
4	D	沒有出邊，沒有更新	[]

Queue 清空就結束了。

可以發現整個過程中，A→B、A→C 這類邊完全沒有被重複檢查多餘的次數，跟 Bellman-Ford 「不管有沒有變化，每輪都重新檢查所有邊」的做法比起來，明顯少做了很多白工。

實作

Python

from collections import deque

def spfa(num_vertices, adjacency_list, start):
    # adjacency_list[u] 是一個 list，內容是 (v, weight)，代表 u -> v 的一條邊
    distances = [float("inf")] * num_vertices
    distances[start] = 0

    in_queue = [False] * num_vertices  # 記錄頂點目前在不在 Queue 裡，避免重複塞入
    queue = deque([start])
    in_queue[start] = True

    while queue:
        u = queue.popleft()
        in_queue[u] = False  # 先標記離開 Queue，之後如果又被更新，才可以重新入列

        for v, weight in adjacency_list[u]:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True

    return distances

JavaScript

function spfa(numVertices, adjacencyList, start) {
  // adjacencyList[u] 是一個陣列，內容是 { node, weight }，代表 u -> node 的一條邊
  const distances = new Array(numVertices).fill(Infinity);
  distances[start] = 0;

  const inQueue = new Array(numVertices).fill(false); // 記錄頂點目前在不在 Queue 裡，避免重複塞入
  const queue = [start];
  inQueue[start] = true;

  while (queue.length) {
    const u = queue.shift();
    inQueue[u] = false; // 先標記離開 Queue，之後如果又被更新，才可以重新入列

    for (const { node: v, weight } of adjacencyList[u]) {
      if (distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
        if (!inQueue[v]) {
          queue.push(v);
          inQueue[v] = true;
        }
      }
    }
  }

  return distances;
}

Java

import java.util.*;

class SPFA {
    static class Edge {
        int node;
        int weight;

        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    static int[] spfa(int numVertices, List<List<Edge>> adjacencyList, int start) {
        int[] distances = new int[numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        boolean[] inQueue = new boolean[numVertices]; // 記錄頂點目前在不在 Queue 裡，避免重複塞入
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        inQueue[start] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false; // 先標記離開 Queue，之後如果又被更新，才可以重新入列

            for (Edge edge : adjacencyList.get(u)) {
                int v = edge.node;
                if (distances[u] + edge.weight < distances[v]) {
                    distances[v] = distances[u] + edge.weight;
                    if (!inQueue[v]) {
                        queue.add(v);
                        inQueue[v] = true;
                    }
                }
            }
        }

        return distances;
    }
}

別忘了 in_queue 這個標記

如果沒有用 in_queue 檢查「這個頂點是不是已經在 Queue 裡了」，同一個頂點可能被重複塞進 Queue 很多次，浪費大量重複運算，這個標記是 SPFA 能夠加速的關鍵之一。

用 Queue 順便偵測負權重環

SPFA 也能偵測負權重環，而且比 Bellman-Ford「多跑一輪」更直覺：額外記錄每個頂點被放入 Queue 的次數，如果同一個頂點被放入 Queue 超過 V 次，代表它的距離被不斷刷新、永遠無法收斂，也就代表圖中存在負權重環（可以從這個頂點往回追出環的位置）。

複雜度

項目	複雜度	說明
平均時間複雜度	近似 O(E)	大部分隨機圖、稀疏圖的情況下，實際跑起來接近這個等級
最壞時間複雜度	O(V × E)	跟 Bellman-Ford 相同等級，某些刻意構造的圖（例如網格圖）會讓 SPFA 退化到跟 Bellman-Ford 一樣慢
空間複雜度	O(V)	Queue、距離陣列、in_queue 標記陣列

新手小提醒

SPFA 的名字裡雖然有個 "Faster"，但它的最壞情況複雜度並沒有比 Bellman-Ford 更好，只是平均情況通常快很多。

只要刻意構造出「網格狀」的圖，就能讓 SPFA 退化到最壞情況，因此在資料可能被刻意出題針對的場合（例如演算法競賽），有些人會選擇直接用 Bellman-Ford 或 Dijkstra（如果沒有負權重）以求穩妥。

適用情況

• 圖中存在負權重，且是稀疏圖：邊的數量遠小於 V² 時，SPFA 平均表現通常比 Bellman-Ford 快上不少。
• 需要偵測負權重環，且想在偵測到當下就提早結束：透過「入列次數超過 V 次」的技巧，通常能比 Bellman-Ford 更快發現負權重環的存在。
• 實作 Bellman-Ford 太慢、但題目又不保證沒有負權重：如果 Dijkstra 因為負權重無法使用，SPFA 通常是比原始 Bellman-Ford 更實際的替代方案。

常見誤區

• 誤以為 SPFA 一定比 Bellman-Ford 快：SPFA 只是平均情況比較快，最壞情況下（例如某些網格圖）複雜度會退化回 O(V × E)，跟 Bellman-Ford 一樣慢，不能無條件假設它一定比較快。
• 忘記處理 in_queue 標記，導致重複入列：如果沒有檢查頂點是否已經在 Queue 裡，同一個頂點可能被重複放入很多次，不只浪費時間，也會讓「入列次數超過 V 次代表負權重環」這個判斷失去意義。
• 把 SPFA 跟 Graph Traversal 的 BFS 搞混：兩者都用 Queue，但 BFS 每個頂點只會被拜訪一次；SPFA 的頂點可能因為距離被多次更新，而被放入 Queue 很多次，這是兩者本質上的差異。
• 圖沒有負權重時還是選擇用 SPFA：如果確定圖中不會有負權重，直接用 Dijkstra 搭配 Min-Heap，時間複雜度 O((V + E) log V) 通常比 SPFA 更穩定、更快。