How to find shortest path in a directed graph that has edge weights either 0 or 1 in linear time?

Question

I am looking for a way to augment the BFS method used to find the single source shortest paths in an unweighted directed graph and solve the above problem in O(N+M) time. where N is the number of vertices, M is the number of edges

I have thought the following:

1. Contract the vertices of the graph that have an edge weight 0 between them. But this would definitely be wrong as then I would be changing the graph's properties and adding new edges to vertices that originally had none.

2. Changing the edge weights to 1 and 2. And then creating dummy vertices in the paths that are of length 2 to convert those edges to edges of weight 1. But this would give the wrong answer.

In more generality, how can I find single source shortest paths in a directed graph when the edge weights are between 0 and MAX in linear time. (MAX is the maximum edge weight)

Answer 1

You can use bfs with some modifications: maintain a deque instead of a queue and add a vertex to the front of the deque if 0 edge is used and to the back of the deque otherwise.(I mean 0-1 case now)

Answer 2

I think you can work this out with vertex contraction. Just a hint here:

First form connected components of vertices that are connected by 0-weight edges and select one representative member in every component. This will give you a contracted graph.

Then solve the unweighted problem.

The true path will be formed of "inter-edges" (weight 1) joining the representative members, and "intra-edges", joining vertices within the component, from the incoming inter-edge to the outgoing inter-edge. In other words, you need to be able to find the path from any representative to any other representative.