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
EXPLANATION:
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.
How?
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.
@ambarpal, there is not much difference between deque and queue. You take vertices from the beginning each time but to deque you can add to the beginning sometimes if the weight of edge is 0 (because there is no difference which vertices of the same level to explore firstly).
Hi @ambarpal I have done it by BFS using a queue. Here is my solution for reference : http://www.codechef.com/viewsolution/4482761 . In the solution graph vector is the input graph and ans[i] stores the length of the shortest path from N to that node so far. It is updated if we find a shorter path. ans[1] will finally store the shortest length from n to 1.
My BFS runs as follows. Reach all the nodes u can with normal paths. If final city is reached, break. Else add 1 to cost and reach all cities you can with a reverse path from current set of cities. Here’s the code: http://www.codechef.com/viewsolution/4471282
Can someone please provide the test case where this solution is failing.http://ideone.com/7347aF
I am storing the undirected version of graph in a vector and applying dijkstra’s finding the shortest path keeping the track of the minimum number of edges to be reversed by checking if the edge (i,j) exists in the input graph(stored in a set).
Is it giving TLE because of the way of implementation?
can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible
and even if it is possible then how???
can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible and even if it is possible then how???
can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible and even if it is possible then how???
Maximum edges are given in the constraints: 10^5. Imagine the edges in terms of their costs. Travelling over a normal edge is 0. Inverting an edge has some cost, some constant value for all reverse edges. You can give it any value. The author has given all reverse edges a value of one because its simple to do so.
A O(V+E) algorithm: Combination of dfs and bfs. Basically in this algo we use dfs to push nodes into the bfs queue… Initially all the nodes which can be visited from vertex node 1 are pushed into the queue with level being equal to 0… Then each time we dequeue and do the dfs of all the elements(if not already visited) which can be visited by reversing the edge with this vertex(This pushes them into the queue) .The level of all these nodes will be level of the dequeued node+1…Do this until the queue empties.The level of the nth node is the answer if it is visited otherwise it is -1.
@adi_das >> for every given edge x->y, add it to the graph with weight 0 and also add a reverse edge y->x with weight 1. So if we are given E edges, after adding them and the reverse edges we will be having a total of 2*E edges, half of them with 0 weight and other half of them with weight 1. Hope this clarifies your doubt.
i have used warshalls algorithm to find the shortest path but my solution gave a wa
i took a 2d matrix and initially i stored INF in matrix then
matrix[x][y]=0; and matrix[y][x]=1;
then i applied kruskals algo
which gave coreect answers for the given test case but wa when i submitted my solution .
A simple question how you get the thought for this like adding a reverse edge with weight 1 this makes the problem very easy. Is this a classical problem or i can use any other apporoach to solve this…please help.