---
# System prepended metadata

title: 0-1 BFS
tags: [內湖高中程式競賽]

---

# 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