0-1 BFS

辺の重みが0または1のグラフで、単一始点最短経路を O(V+E) で求めるアルゴリズム。

通常のBFSと異なり、deque を使用する。

特徴

項目	内容
用途	単一始点最短経路
適用条件	辺の重みが0または1
計算量	O(V+E)
空間計算量	O(V+E)（グラフを含む）

考え方

距離が小さい頂点から探索するため、辺の重みに応じてキューへの追加位置を変える。

• 重み0 → push_front()
• 重み1 → push_back()

これにより、Dijkstraのような優先度付きキューを使わずに処理できる。

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
    }

    const int INF = 1e9;
    vector<int> dist(n, INF);

    auto bfs01 = [&](int s) {
        deque<pair<int, int>> q;
        dist[s] = 0;
        q.push_front({0, s});

        while (!q.empty()) {
            auto [d, v] = q.front();
            q.pop_front();
            if (d != dist[v]) continue;

            for (auto [nv, w] : g[v]) {
                if (dist[nv] <= d + w) continue;
                dist[nv] = d + w;
                if (w == 0) q.push_front({dist[nv], nv});
                else q.push_back({dist[nv], nv});
            }
        }
    };

    bfs01(s);

    for (int v = 0; v < n; v++) {
        if (dist[v] == INF) cout << "INF\n";
        else cout << dist[v] << '\n';
    }
}

使用例

入力（0-indexed、有向グラフ）

5 6 0
0 1 1
0 2 0
2 1 0
1 3 1
2 3 1
3 4 0

出力

0
0
0
1
1

注意点

• 辺の重みが0または1の場合にのみ使用できる。
• queue ではなく deque を使う。
• BFSと違い、頂点を一度訪問しただけでは最短距離が確定しない。
• dist[nv] が改善された場合のみキューに追加する。
• キューに古い距離情報が残るため、取り出した距離が現在の dist[v] と異なる場合はスキップする。
• 無向グラフの場合は逆向きの辺も追加する。

最短経路アルゴリズムの使い分け

アルゴリズム	辺の重み	計算量
BFS	重みなし	O(V+E)
0-1 BFS	0または1	O(V+E)
Dijkstra	非負	O((V+E) log(V+E))
Bellman-Ford	負辺も可	O(VE)

関連

• BFS
• Dijkstra