Graph, Shortest Path Algorithms
A directed graph with N vertices and M edges is given.
What is the minimum number of edges he needs to reverse in order to have at least one path from vertex 1 to vertex N, where the vertices are numbered from 1 to N?
1 ≤ N,M ≤ 105
Add reverse edge of each original edge in the graph. Give reverse edge a weight=1 and all original edges a weight of 0. Now, the length of the shortest path will give us the answer.
If shortest path is p: it means we used k reverse edges in the shortest path. So, it will give us the answer.
The shortest path algorithm will always try to use as less reverse paths possible because they have higher weight than original edges.
To find shortest path, we can use Dijkstra’s Algorithm which works in O(|E| log |V|) if implemented using adjacency lists and priority queue.
Also, since there are only 0 and 1 weight edges, we can also do this by BFS: 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.