Graph Algorithms · 比較表
最短路徑演算法比較
BFS、Dijkstra、Bellman-Ford、Floyd-Warshall、DAG 最短路徑：邊權、負邊、單源或全點對，一張表看完該用哪一個。
| 演算法 | 時間 | 空間 | 邊權 | 負邊 | 範圍 | 難度 |
|---|---|---|---|---|---|---|
| BFS廣度優先搜尋 | O(V+E) | O(V) | 全部相同（無權） | — | 單源 | 入門 |
| Dijkstra單源最短路徑 | O((V+E) log V) | O(V) | 非負 | ✗ | 單源 | 進階 |
| Bellman-Ford含負權最短路徑 | O(VE) | O(V) | 任意 | ✓，且能偵測負環 | 單源 | 困難 |
| Floyd-Warshall全點對最短路徑 | O(V³) | O(V²) | 任意 | ✓（負環看對角線） | 全點對 | 困難 |
| Shortest Path in DAGDAG 最短路徑 | O(V+E) | O(V) | 任意 | ✓（無環所以沒有負環） | 單源 | 進階 |
什麼時候選哪一個
BFS 廣度優先搜尋
每步成本一樣：格子圖、社交距離、狀態轉移次數。最短路徑問題裡最快的一個，能用就用。
Dijkstra 單源最短路徑
有權圖的預設：地圖、網路延遲、加權狀態圖。一條負邊就會錯，而且不會報錯。
Bellman-Ford 含負權最短路徑
有負邊、要偵測負環（套利、匯率）、或「最多走 k 步」這種限制。V·E 很慢，V 上萬就要考慮換。
Floyd-Warshall 全點對最短路徑
要所有點對的距離、V ≤ 400 左右、或圖很稠密。三層迴圈五行寫完，不會寫錯。
Shortest Path in DAG DAG 最短路徑
圖保證無環：任務排程、關鍵路徑、DP 狀態圖。拓撲序鬆弛一遍 O(V+E)，還能求最長路徑。
選擇指南
- 無權 → BFS。非負權 → Dijkstra。有負邊 → Bellman-Ford。無環 → DAG 拓撲鬆弛。全點對且 V 小 → Floyd-Warshall。
- 邊權只有 0 和 1 → 0-1 BFS（deque，權 0 放前面、權 1 放後面），O(V+E) 而不用 Dijkstra 的 log。
- 全點對但 V 大、邊稀疏 → 對每個點跑一次 Dijkstra，V·(V+E) log V 通常比 V³ 快得多。
- 最長路徑 → 一般圖是 NP-hard；DAG 上把邊權取負跑最短路徑，或直接在拓撲序上取 max。
- 只要知道能不能到、不在乎距離 → DFS 或 Union-Find 就夠，不必上最短路徑。