1. Dijkstra 演算法 (Dijkstra’s Algorithm)

核心概念： 貪婪策略 (Greedy) + 優先佇列 (Priority Queue)。 適用場景： 非負權重圖的單源最短路徑 (Single-Source Shortest Path, SSSP)。 核心邏輯： 每次從「未訪問集合」中選取距離起點最近的節點，對其鄰居進行鬆弛 (Relaxation)。

  • 時間複雜度： $O(E \log V)$ (使用 Min-Heap)
  • 空間複雜度： $O(V + E)$

2. Bellman-Ford 演算法

核心概念： 動態規劃 / 暴力鬆弛。 適用場景： 含負權邊的單源最短路徑，可檢測負權環 (Negative Cycle)。 核心邏輯： 對所有邊進行 $V-1$ 次鬆弛操作。若第 $V$ 次仍能鬆弛，則存在負環。

  • 時間複雜度： $O(VE)$
  • 空間複雜度： $O(V + E)$

3. SPFA 演算法 (Shortest Path Faster Algorithm)

核心概念： Bellman-Ford 的佇列優化版本。 適用場景： 含負權邊但無負環的圖，且圖非稠密網格圖 (Grid Graph)。 核心邏輯： 只有當節點 $u$ 被鬆弛變小後，其鄰居才有可能變小。僅將被更新過且不在佇列中的節點加入佇列。

  • 時間複雜度： 平均 $O(kE)$ ($k$ 為常數，通常很小)，但在特製測資(稠密圖/網格圖)下會退化至 $O(VE)$。
  • 注意： 現代競賽中容易被卡 (Time Limit Exceeded)，非必要請優先使用 Dijkstra。

4. Floyd-Warshall 演算法

核心概念： 動態規劃 (Dynamic Programming)。 適用場景： 全對最短路徑 (All-Pairs Shortest Path, APSP)，節點數少 ($V \le 500$)。 核心邏輯： $dp[k][i][j]$ 表示從 $i$ 到 $j$ 只經過前 $k$ 個節點的最短路徑。 狀態轉移方程：$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$。

  • 時間複雜度： $O(V^3)$
  • 空間複雜度： $O(V^2)$

總結比較表 (Comparison)

算法 類型 邊權限制 時間複雜度 適用情境
Dijkstra SSSP 非負 $O(E \log V)$ 一般最短路首選，地圖導航。
Bellman-Ford SSSP 可負 $O(VE)$ 需檢測負環或邊數極少時。
SPFA SSSP 可負 Avg $O(kE)$, Max $O(VE)$ 隨機圖快，但在競賽中易被卡。
Floyd-Warshall APSP 可負 $O(V^3)$ 點數少 ($N \le 500$) 的全對最短路。 
import heapq
from copy import deepcopy


def dijkstra(graph: dict[int, list[tuple[int, int]]],
             start: int) -> dict[int, int]:
  dist = {i: float('inf') for i in graph}
  dist[start] = 0
  pq = [(0, start)]
  while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
      continue
    for v, w in graph[u]:
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        heapq.heappush(pq, (dist[v], v))
  return dist


def bellman_ford(graph: dict[int, list[tuple[int, int]]],
                 start: int) -> dict[int, int]:
  dist = {i: float('inf') for i in graph}
  dist[start] = 0
  for _ in range(len(graph) - 1):
    for u in graph:
      for v, w in graph[u]:
        if dist[u] + w < dist[v]:
          dist[v] = dist[u] + w
  return dist


def spfa(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
  dist = {i: float('inf') for i in graph}
  dist[start] = 0
  pq = [start]
  while pq:
    u = pq.pop(0)
    for v, w in graph[u]:
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        pq.append(v)
  return dist


def floyd_warshall(graph: list[list[int]]) -> list[list[int]]:
  dist = deepcopy(graph)
  for k in range(len(graph)):
    for i in range(len(graph)):
      for j in range(len(graph)):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  return dist