How to find the shortest path in an oriented graph that has the weight of edges, either 0 or 1 in linear time?

Question

I am looking for a way to increase the BFS method used to find the shortest paths of a single source 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 thought the following:

• Contract the vertices of the graph that have an edge weight of 0 between them. But this would definitely be wrong, since then I would change the properties of the graph and add new edges to the vertices that I did not initially have.

• Change the weights of the edges by 1 and 2. Then create fictitious vertices in paths of length 2 to convert these edges to the edges of weight 1. But this would give the wrong answer.

More generally, how can I find the shortest paths of a single source in a directed graph, when the weight of the edges is between 0 and MAX in linear time. (MAX - maximum edge weight)

Answer 1

You can use bfs with some changes: save the deck instead of the queue and add a vertex to the front of the deque, if edge 0 is used, and back to the back of the detex (I mean case 0-1)

Answer 2

I think you can do this with vertex reduction. Just a hint here:

First vertex connected components connected by 0-weight edges, and select one representative element in each component. This will give you an abbreviated schedule.

Then solve the unweighted problem.

The true path will be formed from the "intercostal space" (weight 1) connecting the representative members, and the "intercostal space" connecting the vertices inside the component, from the incoming intercostal space to the outgoing intercostal space. In other words, you need to find a way from any representative to any other representative.

Answer 3

Sorry, but in such complexity it should not be possible.

You can refer to this table for the complexity of the shortest path algorithms.

As you explain the problem, you want to keep the weights 0 and 1. If you can afford to remove the edges of 0 weights, it degenerates to the shortest path with unweighted edges that must be at the same complexity. (First the width of the search will be the keyword then)