Last Updated: 5 Dec, 2020
Path Reversals
Moderate
Asked in company
You are given a directed graph and two nodes, ‘S’ and ‘D’, denoting the start and end node. Your task is to find the minimum number of edges that you have to reverse to find the path from nodes 'S' to 'D'.
For example:
Let's consider 'S' = 0 and 'D' = 4. In the above graph, the path from nodes 0 to 4 can be created by only reversing the edge (0, 5). Hence, the answer is 1.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of nodes and edges in the graph.
The following M lines of the test case contain two space-separated integers, ‘A’ and ‘B’, representing an edge from node ‘A’ to node ‘B’.
The last line of the test case contains two space-separated integers, ‘S’ and ‘D’, denoting the start and end node.
Output Format:
For each test case, print a single integer, i.e., the minimum number of edges to be reversed, so the path exists from ‘S’ to ‘D’.
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
2 <= N <= 10^5
N - 1 <= M <= 10^5
0 <= A, B < N
0 <= S, D < N
Time Limit: 1 sec
Approaches
In this approach, we make the graph into a weighted graph. We set the edges’ edge-weight as 0 and add all the reverse edges with weight 1.
We will apply the Bellman-Ford algorithm on the start node and get the distance from all the nodes in the graph. Each time a reversed edge is traversed in the path, the path cost will increase by 1.The total path cost gives the number of reversed edges used in getting the path from source to destination.
We will create a function bellmanFord(edges, n, source). The parameter edge is the edge list, n is the number of nodes, and the source is the starting node. This function will return the list of distances of all nodes from the source.
Algorithm:
- The function bellmanFord(edges, n, source): where the parameter edges, is the edge list, n is the number of nodes, and the source is the starting node.
- Create a distances list of length n with all values initialized to the maximum value of the integer.
- Set the distance of source distances[source] as 0
- Iterate from 0 to n - 1
- Iterate edge through the array edges
- Set currentSource as edge[0]
- Set destination as edge[1].
- Set weight as edge[3].
- Set distances[destination] as the minimum of distances[destination] and the sum of distances[currentSource] and weight.
- Iterate edge through the array edges
- After the while loop ends, return the list distances.
- Make a list newEdges.
- Iterate through a list of Edges, and for each edge.
- Append 0 to edge, Append it to newEdges array.
- Make a newEdge list as [edge[1], edge[0], 1], to make the reverse edge with weight 1. Append newEdge to newEdges.
- Call the bellmanFord(newEdges, N, S) function, which returns the distances of all nodes from the source nodes S and stores the output as pathList.
- We will return pathList[D]. That represents the distance of ‘S from node D.
In this approach, we make the graph into a weighted graph. We set the edges’ edge-weight as 0 and add all the reverse edges with weight 1.
We will apply Dijkstra’s algorithm on the start node and get the distance from all the nodes in the graph. Each time a reversed edge is traversed in the path, the path cost will increase by 1. The total path cost gives the number of reversed edges used in getting from source to destination.
We will create a function dijkstra(graph, n, source). The parameter graph is the adjacency list, n is the number of nodes, and the source is the starting node. This function will return the list of distances of all nodes from the source.
Algorithm:
- The function dijkstra(graph, n, source): where graph is the adjacency list, n is the number of nodes, and the source is the starting node.
- Create a distances list of length n with all values initialized to the maximum value of the integer.
- Set the distance of source distances[source] as 0
- Initialize a priority queue pq. Each value is a list of 2 numbers in the queue first represents the distance(priority), and the second is the node.
- Add start node to pq. Insert [0, source] in pq.
- While pq size of greater than 0.
- Get the top element curr from the front of pq. Get current node and current node’s distance from curr. Set currentNode as curr[1] and currentDistance as curr[0].
- If the current node’s distance is larger than in the distances list, then move to the next node.
- Otherwise, iterate through all the neighbours of the current node to get their distance. Set the variable neighbourDistance as graph[currentNode][neighbour] + currentDistance.
- We will check if distances[neightbour] are less than neighbourDistance.
- Update distances[neighbour] as neighbourDistance.
- Create an array li containing a tuple of neighbourDistance and neighbour. Then add the list li to pq.
- After the while loop ends, return the list distances.
- Make a list newEdges.
- Iterate through a list of Edges, and for each edge.
- Append 0 to edge, Append it to newEdges list.
- Make a newEdge list as [edge[1], edge[0], 1], to make the reverse edge with weight 1. Append newEdge to newEdges.
- Make an adjacency list graph by iterating through the newEdges list.
- For each node, add the destination node and the weight as a list. We will insert array of edge[1] and edge[2] in graph[edge[0]], here edge[2] is the weight of the edge from edge[0] to edge[1].
- Call the dijkstra(graph, N, S) function, which returns the distances of all nodes from the source nodes S and store the output as pathList.
- We will return pathList[D]. That represents the distance of ‘S from node D.