How to find shortest path in a directed graph that has edge weights either 0 or 1 in linear time?
algorithm, graph, shortest-path
Solution
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)
Problem
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: 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. 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)