# 0-1 BFS 0-1 BFS 是一個找最短路徑的演算法，他要處理的問題很簡單: 「給定一張有向圖，與一個起點 $s$，每條邊的邊權只會是 $0$ 或 $1$，請求出單源最短路徑」 ## 想法 想當然，我們可以直接使用 [Dijkstra 演算法](https://hackmd.io/@ShanC/Dijkstra) 求出答案，但是這樣時間就會多出一個 $\log$，很不划算 我們可以重新省視一下題目，通常最短路徑中我們會想要用 `priority_queue` 是因為每次取出來會是最小。但我們現在的邊權僅有 $0$ 或 $1$ 而已，只要碰到 $1$ 的那條邊，權重和就會變大，因此我們不需要像 Dijkstra 一樣維護「加到目前的權重和」，直接維護「眼前這條邊的權重」即可。所以可以考慮利用一個容器，頭放權重 $+0$ 的點，尾忘權重 $+1$ 的點，並且每次取頭的元素就好 ## 演算法 實作上我們可以使用 `deque` 來當作這個容器。老樣子 `dis[]` 是距離陣列，`g[]` 是圖 ```cpp= vector<int> bfs01(int s) { vector<int> dis(n, INF); dis[s] = 0; deque<int> q; q.push_front(s); while (!q.empty()) { int v = q.front(); q.pop_front(); for (auto edge : g[v]) { int u = edge.first, w = edge.second; if (dis[v] + w < dis[u]) { dis[u] = dis[v] + w; if (w) q.push_back(u); // w==1 放尾 else q.push_front(u); // w==0 放頭 } } } return dis; } ``` ## 時間複雜度 設 $n$ 為點數、$m$ 為邊數 時間複雜度: $O(n+m)$ ## 備註 有一個拓展的演算法叫 Dial's algorithm，他的想法很簡單，只要邊權 $\le k$，那就直接開 $k$ 個 queue。由於我打競程到現在還沒遇過，所以就不寫囉 ## 題目練習 [codeforces 1063B - Labyrinth](https://codeforces.com/contest/1063/problem/B) [AtCoder Beginner Contest 246E - Bishop 2](https://atcoder.jp/contests/abc246/tasks/abc246_e) [AtCoder アルゴリズムと数学　演習問題集 048 - Small Multiple](https://atcoder.jp/contests/math-and-algorithm/tasks/arc084_b) (這題其實也可以 Dijkstra，取決於你怎麼建圖) ---- ## 參考資料 [CP-algorithms - 0-1 BFS](https://cp-algorithms.com/graph/01_bfs.html) [海大競程 2025 I2CP 講義 - shortest path](https://hackmd.io/@LeeShoWhaodian/HyT4ib5qJg) ---- > [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2026/1/29