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)