Generalized 0-1 BFS Algorithm

2022/09/01

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 \(\{X, Y\}\) such that \(X, Y \ge 0\). 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 is to use Dijkstra’s algorithm, which has a time complexity of \(O(E * logV)\) for the binary heap implementation. Further optimisations such as using Fibonacci heaps is possible, but it has a larger constant factor for practical use cases.

Let us try to see how we can use the concepts involved in both Dijkstra’s algorithm and 0-1 BFS algorithm to optimize our algorithm for this problem.

Optimized Solution

Let’s define two queues \(Q_X\) and \(Q_Y\). Suppose we are at an arbitrary node \(U\) and we are able to reduce the distance to node \(V\) by travelling over an edge from \(U\). If this travelled edge from \(U\) to \(V\) has a weight \(X\) then push \(V\) to the queue \(Q_X\), else push it on the queue \(Q_Y\). In short, \(Q_X\) stores information of all nodes whose current minimum is achieved by last travelling over an \(X\) weighted edge and \(Q_Y\) stores the information of nodes having last weighted edge as \(Y\).

Similar to Dijkstra, at every step:

The main bottleneck is finding the vertex at smallest distance efficiently. If we can keep the two queues individually sorted, then we can solve this part in \(O(1)\) by finding the minimum of the element at the front of each queue.

Claim: During the execution of above algorithm, the queues \(Q_X\) and \(Q_Y\) are always sorted.

Proof: Let us assume that the first inversion has just occurred in \(Q_X\). Let the last appended vertex be \(V\) and the second last appended vertex be \(U\). So, \(dist(U) > dist(V)\). Since the last travelled edge for both these vertices with weight \(X\), we can subtract this quantity from both the distances and get \(dist(U) - X > dist(V) - X\). If we substitute \(pre(A) = dist(A) - X\), then we get \(pre(U) > pre(V)\) at the point of inversion.

\(pre(U)\) and \(pre(V)\) must have been popped from one of the two queues \(Q_X\) and \(Q_Y\). They cannot be popped from the same queue, since we assumed the two queues were always sorted before this moment of time. Hence, they must be from two different queues. But according to our algorithm, we always take the vertex at minimum distance of the two queues. So, if \(pre(U)\) was taken before \(pre(V)\), then \(pre(U) \le pre(V)\). This contradiction proves that \(Q_X\) is always sorted. We can use a similar argument for the other queue.

Analysis

We will visit every vertex at most once and travel every edge at most twice (assuming undirected edges). For every edge we travel, we will push at most one vertex in one of the queues. Hence the amortized time complexity is \(O(V + E)\).

Pseudocode

queue QX , QY
push source S to QX
while one of the two queues is not empty:
    u = pop minimal distant node among the two queue heads
    for all edges e of form (u,v):
        if dist(v) > dist(u) + e.weight:
            dist(v) = dist(u) + e.weight;
            if e.weight == X:
                QX.push(dist(v),v);
            else:
                QY.push(dist(v),v);

Further extension

You can easily extend this to \(K\) distinct edge weights as well. The time complexity of such an approach would be \(O(V + E \cdot logK)\). It is possible that this approach would be faster than Dijkstra for some graphs. The proof and implementation details are left as an exercise for the reader.

Problems

You can practice on problems required for 0-1 BFS:

Happy coding!