0-1 BFS Algorithm

2022/05/10

Note: For discussion, please jump to the blog on Codeforces. This post is re-written and hence a bit more refined, but carries the same underlying idea.

Pre-requisites

Problem

You have a graph \(G\) with \(V\) vertices and \(E\) edges. Edges of the graph are weighted, and the edge weights belong to the set \(\{0, 1\}\). You are given a source vertex \(S\) and a destination vertex \(D\). Find the shortest path between the two vertices.

Naive Solution

The straightforward solution to this problem is Dijkstra’s algorithm, which has a time complexity of \(O(E * logV)\) with binary heaps and \(O(E + V * logV)\) with fibonacci heaps.

Pseudocode

for all v in vertices:
    dist[v] = inf
    seen[v] = False

queue q
dist[source] = 0;
q.push(source, dist[source])

while d.empty() == false:
    vertex = q.front()
    q.pop()

    if seen[vertex]:
        continue

    for all edges e of form (vertex , u):
        if dist[u] > dist[vertex] + e.weight:
            dist[u] = dist[vertex] + e.weight
            q.push(u, dist[u])

    seen[vertex] = True

While this is a fairly efficient solution, we can further improve the time complexity of our solution by focusing on one important detail – the edge weights are either 0 or 1.

Optimized Solution

Revisiting BFS algorithm

At a high level, BFS and Dijkstra are fairly similar algorithms. They both keep a queue of vertices to be visited sorted by their level (or distance) from the source vertex, and process vertices in increasing distance from the source vertex.

Lemma: During the execution of BFS, the queue holding the vertices only contains elements from at max two successive levels of the BFS tree.

Proof: Consider any moment of execution of BFS on a graph (with edge weight = 1). Let’s assume that the topmost vertex \(U\) in our queue \(Q\) is at a distance \(D\) from the source vertex \(S\). Suppose a vertex \(V\) exists in our queue at a distance \(D + 2\) from the source vertex. This means that we have already visited a vertex at a distance \(D + 1\) from the source vertex, which is a contradiction since our queue is sorted and we visit vertices in increasing order of distance.

Similarity between BFS and our problem

The main observation is that since edge weights are limited to 0 or 1, everytime we relax the distance to a vertex \(V\) from a vertex \(U\) then \(dist[U] \le dist[V] \le dist[U] + 1\). This means, every new explored vertex \(V\) is either at the same distance as \(U\) or exactly 1 more. Using the above lemma, we can prove that the queue used in our above Dijktra implementation will only contain vertices at distance \(dist[U]\) or \(dist[U] + 1\) (in a sorted order) when we are exploring vertex \(U\).

We can start to see that it is easy to keep the queue sorted without advanced data structures such as binary heap. To insert a new vertex \(V\) in our queue, we can either push it to the front of our queue (if \(dist[V] = dist[U]\)) or to the back of our queue (if \(dist[V] = dist[U] + 1\)) and our queue will remain sorted! If we can do this faster than \(O(logV)\), then we can improve on our initial Dijkstra implementation.

We need a data structure that supports the following operations in better than \(O(logV)\) time:

All of the above operations can be done in \(O(1)\) with a doubly ended queue (or deque in C++ STL).

Analysis

Similar to Dijkstra’s algorithm:

Hence, the amortized time complexity of the algorithm is \(O(E + V)\), which is more efficient that Dijkstra’s algorithm.

The proof of correctness is relatively straightforward. Since our deque is always sorted, our algorithm is essentially equivalent to Dijkstra’s algorithm for the given problem, albeit with an optimized data structure.

Pseudocode

for all v in vertices:
    dist[v] = inf
    seen[v] = False

dequeue d
dist[source] = 0;
d.push(source)

while d.empty() == false:
    vertex = d.front()
    d.pop()

    if seen[vertex]:
        continue

    for all edges e of form (vertex , u):
        if dist[u] > dist[vertex] + e.weight:
            dist[u] = dist[vertex] + e.weight
            if e.weight == 1:
                q.push_back(u)
            else:
                q.push_front(u)

    seen[vertex] = True

Practice

Before moving into solving problems from online judges, try to prove the following statements about 0-1 BFS algorithm:

Some relevant problems:

Div1 — 500 on TopCoder are tough to crack, so congrats on being able to solve one of them using a simple algorithm. Happy Coding!