0–1 BFS

When every edge costs 0 or 1, a deque finds shortest paths without a heap.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Start with source distance 0.
2. Relax edges exactly as in shortest-path algorithms.
3. Push a zero-cost improvement to the front and a one-cost improvement to the back.
4. The deque processes distance layers in nondecreasing order.
5. A zero-cost improvement stays in the current distance layer at the deque front. A cost-one improvement belongs at the back. Stale entries are ignored.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: A zero-cost improvement stays in the current distance layer at the deque front. A cost-one
// improvement belongs at the back.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
vector<int>zeroOne(const vector<vector<pair<int,int>>>&g,int s){
    const int INF=1000000000;
    vector<int>d(g.size(),INF);
    deque<pair<int,int>>q;
    d[s]=0;
    q.push_front({0,s});
    while(!q.empty()){
        auto[dv,v]=q.front();
        q.pop_front();
        if(dv!=d[v]){
            continue;
        }
        for(auto[u,w]:g[v]){
            if(d[u]>dv+w){
                d[u]=dv+w;
                if(w==0){
                    q.push_front({d[u],u});
                }
                else{
                    q.push_back({d[u],u});
                }
            }
        }
    }
    return d;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source;
    cin>>n>>m>>source;
    vector<vector<pair<int,int>>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b,weight;
        cin>>a>>b>>weight;
        graph[a].push_back({b,weight});
    }
    vector<int>distance=zeroOne(graph,source);
    for(int vertex=1;vertex<=n;vertex++){
        if(vertex>1){
            cout<<' ';
        }
        if(distance[vertex]==1000000000){
            cout<<"INF";
        }
        else{
            cout<<distance[vertex];
        }
    }
    cout<<'\n';
}

Complexity analysis

O(V + E) time, O(V + E) space for lazy entries.

Example input and output

Read n m source and m directed edges a b weight. Require 1≤n≤200000 and each weight to be 0 or 1. Print distances to labels 1..n, using INF for unreachable vertices.

Input

4 4 1
1 2 1
1 3 0
3 2 0
2 4 1

Output

0 0 0 1

The zero-cost route 1→3→2 beats the direct cost-one edge. Reaching 4 then costs one.

Practical applications

Use 0–1 BFS for graphs whose edge costs are exclusively zero and one; use a priority queue for more general costs.

Check your understanding

Where does a zero-weight relaxation go?

Put it into practice

A directed road may be reversed at cost 1. Find the minimum reversals needed to reach a target.