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

8
votes

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)

3
algorithmgraphshortest-path
BTW in the general case you get O((n + m) log n) with Dijkstra using a binary heap as priority queue. If MAX is really small, you could use buckets and a y-fast trie to implement the prio queue, resulting in O(n) space and a O((n + m) * log log (n * MAX)) time (no idea how fast that would be in practice, but I'd really like to know :D) – Niklas B.
Torben Hagerups explanations on Improved Shortest Paths on the Word RAM may be helpful to you. – SpaceTrucker
If you only have MAX different lengths, you can have one queue for vertices at each distance. Basically you're making a constant time priority queue. – Thomas Ahle

3 Answers

10
votes

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)

0
votes

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.

-1
votes

I'm sorry but in this complexity, this shouldn't be possible.

You can take a look at this tabular for complexitys of shortest path algorithms

As you explain the problem you want to keep the weights of 0 and 1. If you can afford removing the 0 weight edges, this degenerates to a shortest path with unweighted edges which should be solvanle with your desired complexity.(Breadth first search would be the keyword then)