Path Reversals
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

Question

Path Reversals

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:

graph1

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

Accepted Answer

The task is to find the minimum number of edges that need to be reversed in a directed graph to find the path from a start node to an end node.

The problem can be solved using graph traversal algorithms like Breadth First Search (BFS) or Depth First Search (DFS).
Start by creating an adjacency list representation of the directed graph.
Perform a BFS or DFS from the start node to the end node, keeping track of the number of edges reversed.
Return the minimum number of edges reversed to reach the end node.

Accepted Answer

Bellman-Ford Algorithm

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.
- 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.

Space Complexity: O(n)Explanation:

O(N + M), Where N and M are the numbers of nodes and edges in the graph.

We are maintaining a distances array that takes O(N) space. The O(M) space complexity is used to maintain the edges array. Hence the overall space complexity becomes O(N).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), Where N and M are the numbers of nodes and edges in the graph.

We are doing N iterations, and in each iteration, we are traversing through the edges that take O(M) time. Hence, the overall time complexity becomes O(N*M).

Java (SE 1.8)


/*
Time Complexity: O(N*M)
Space Complexity: O(N + M)

Where N and M are the number of nodes and edges in the graph
*/

import java.util.Arrays;
public class Solution {

	// BellmanFord function on the graph

	public static int[] bellmanFord(int[][] edges, int n, int source) {

		int distances[] = new int[n];
		Arrays.fill(distances, 10000000);

		// Set distance of source as 0
		distances[source] = 0;

		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < edges.length; j++) {
				int[] edge = edges[j];

				// Get the source, destination and weight of the edge
				int currentSource = edge[0];
				int destination = edge[1];
				int weight = edge[2];

				// Update the minimum distance of destination
				distances[destination] = Math.min(distances[destination], distances[currentSource] + weight);
			}
		}

		// Return the array of distances
		return distances;
	}

	public static int pathReversal(int n, int m, int[][] edges, int s, int d) {

		// Make the new Edges array
		int[][] newEdges = new int[2 * (edges.length)][];

		// Marker index to maintain the index
		int newEdgesMarkingIndex = 0;

		for (int i = 0; i < edges.length; i++) {
			int[] edge = new int[edges[i].length + 1];

			for (int j = 0; j < edges[i].length; j++) {
				edge[j] = edges[i][j];
			}

			// Add weight 0 to every edge
			edge[edge.length - 1] = 0;

			// Make reversed edge with weight 1
			int[] newEdge = { edge[1], edge[0], 1 };

			newEdges[newEdgesMarkingIndex++] = edge;
			newEdges[newEdgesMarkingIndex++] = newEdge;
		}

		int pathList[] = bellmanFord(newEdges, n, s);

		// Return the distance of node d from s
		return pathList[d];
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*M)

    Space Complexity: O(N + M)



    Where N and M are the number of nodes and edges in the graph



*/



// BellmanFord function on the graph

vector bellmanFord(vector> &edges, int n, int source)

{

    vector distances(n, 10000000);



    // Set distance of source as 0

    distances[source] = 0;



    for(int i = 0; i < n - 1; i++)

    {   

        for(int i =0; i < edges.size(); i++)

        {   

            vector edge = edges[i];



            // Get the source, destination and weight of the edge

            int currentSource = edge[0];

            int destination = edge[1];

            int weight = edge[2];



            // Update the minimum distance of destination

            distances[destination] = min(distances[destination], distances[currentSource] + weight);

        }

    }



    // Return the array of distances

    return distances;

}



int pathReversal(int n, int m, vector> &edges, int s, int d)

{

    // Make the new Edges array

    vector> newEdges;



    for (int i = 0; i < edges.size(); i++) 

    {

        vector edge = edges[i];



        // Add weight 0 to every edge

        edge.push_back(0);



        // Make revesed edge with weight 1

        vector newEdge = {edge[1], edge[0], 1};



        newEdges.push_back(edge);

        newEdges.push_back(newEdge);

    }



    vector pathList = bellmanFord(newEdges, n, s);



    // Return the distance of node d from s

    return pathList[d];

}

Python (3.5)

'''

    Time Complexity: O(N*M)

    Space Complexity: O(N + M)



    Where N and M are the number of nodes and edges in the graph



'''



from sys import maxsize



# BellmanFord function on the graph

def bellmanFord(edges, n, source):



    distances = [maxsize for i in range(n)]



    # Set distance of source as 0

    distances[source] = 0



    for i in range(n - 1):

        

        for edge in edges:



            # Get the source, destination and weight of the edge

            currentSource = edge[0]

            destination = edge[1]

            weight = edge[2]



            # Update the minimum distance of destination

            distances[destination] = min(distances[destination], distances[currentSource] + weight)



    # Return the array of distances

    return distances



def pathReversal(n, m, edges, s, d):



    # Make the new Edges array

    newEdges = []



    for edge in edges:



        # Add weight 0 to every edge

        edge.append(0)



        # Make reverse edge with weight 1

        newEdge = [edge[1], edge[0], 1]



        newEdges.append(edge)

        newEdges.append(newEdge)



    pathList = bellmanFord(newEdges, n, s)



    # Return the distance of node d from s

    return pathList[d]

Accepted Answer

Dijkstra’s Algorithm

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.

Space Complexity: O(n)Explanation:

O(N + M), where N and M are the numbers of nodes and edges in the graph.

We are storing the graph is in an adjacency list that takes O(N + M) space. The priority queue and distances array takes O(N) space. Hence, the overall space complexity O(N + M + 2*N) = O(N + M).

Time Complexity: OtherExplanation:

O((N + M)*log(N)), where N and M are the numbers of nodes and edges in the graph.

The time complexity of insert, delete operations on the priority queue is O(log(N)).

The time complexity of the Dijkstra Algorithm:

N times delete operation while extracting the minimum value node :O(N *log(N))

M times insert operation while traversing neighbour node: O(M*log(N))

Hence, the overall time complexity of the Dijkstra Algorithm is O((N + M)*log(N)).