Minimum Edges to Reverse to Make the Path from a Source to a Destination

Problem Statement

Minimum edges to reverse to make the path from a source to a destination.

We have to determine how many edges must be reversed in a directed graph with a source node and a destination node to create at least one path between them.

Explanation

Consider the following directed graph, where the source node is 0 and the destination node is 6.

There are two routes from source to destination in the graph above: 

First Path: 0 → 1 → 2 → 3 → 6
Second Path: 0 → 1 → 4 → 5 → 6

Only two graph edges must be reversed in the First Path, making the required minimum number of reversed edges just 2.

Reversing the edges to create a path from source to destination produces a graph as a result.

Approach

The 0-1 BFS concept would be a more effective solution to this problem.

0-1 BFS concept

When a peer gets a request, it forwards it to all the peers except the sender and looks for appropriate matches. Assume that all the peers are nodes (computers or mobile devices). When a node creates a request message, it is propagated to all its neighbours (other peers). This summarises how BFS is used in the actual world, so hold that notion.

A graph traversal approach called breadth-first traversal explores every node from a root (source) node to nearby nodes. Once all nodes have been visited, it moves on to the next one that is closest and investigates all new nodes.

BFS, in its simplest form, is a graph traversal in which nodes are visited in the graph in increasing order of their distance from the source node.

Due to the fact that we only have the weights 0 and 1, anytime we come across a node connected by a 0 weight edge, we push that node in front of the deque; otherwise, we push it at the end of the deque. A similar strategy can be generalised for any di-weighted network by pushing the node associated with a smaller weight edge at the front and greater weight at the end. Pushing nodes in this manner always results in deque being sorted and we overcome the sorting necessary at each iteration.

Algorithm

• Take input from all the Edges.
   
• Now we will create a function in which we get the minimum reverse edges.
   
• Make the provided graph bidirectional.
   
• Apply 0-1 BFS now to obtain the shortest path using a deque.
   
• When implementing, we will only include a node in the deque if and only if The distance at which it was previously examined was strictly more significant than The distance at which it is now encountered.
   
• All nodes' distances should be set to infinity.
   
• Set the source node's distance to 0.
   
• Iterate through the current node's neighbours
   
• It is necessary to give the original edges a weight of 0.
   
• If the neighbour was visited, create a false edge and give it a weight of 1, then don't add it to the queue again.
   
• Return the max Va,lue
  
  Must Read  C Program to Reverse a Number

Code implementation

/*Minimum edges to reverse to make path from a source to a destination*/

import java.util.*;

class Node {
	private int value;
	private int weight;
	private Integer parent;
	Node(int value, int weight) {
		this.value = value;
		this.weight = weight;
		parent = null;
	}

	/* To prevent a child from visiting its parent and shoving them into the deque during the 0-1 BFS, we employed the idea of the parent. */
	Node(int value, int distance, Integer parent) {
		this.value = value;
		this.weight = distance;
		this.parent = parent;
	}

	public int getTheVal() {
		return value;
	}

	public int getTheWeight() {
		return weight;
	}

	public Integer getTheParent() {
		return parent;
	}
}

class Main {
	public static void main(String[] args) {
		List<List<Integer>> graph_adj = new ArrayList<>();
		for (int i = 0; i<7; i++)
			graph_adj.add(new ArrayList<>());

		graph_adj.get(0).add(1);

		graph_adj.get(2).add(1);

		graph_adj.get(5).add(1);

		graph_adj.get(2).add(3);

		graph_adj.get(6).add(3);

		graph_adj.get(6).add(4);

		graph_adj.get(4).add(5);

		int answer = revMinEdgesGet(graph_adj, 0, 6);

		if (answer == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
	}

	private static int revMinEdgesGet(List<List<Integer>> graph_adj, int search, int end_dest) {
		int n = graph_adj.size();

		//Make the provided graph bidirectional.
		List<List<Node>> newAdj = biDirectionalGraphGet(graph_adj);

		/*
		Apply 0-1 BFS to obtain the shortest path using a deque. If the distance at which it was previously explored was strictly more significant than the distance being encountered, we would merely include the encountered node into the deque in the implementation.
		*/
		Deque<Node> dq = new LinkedList<>();

		/* The elements that make up Node, in this case, are: Node(int node val, int node distance, int node parent)
		 */
		dq.offer(new Node(search, 0, 0));
		int[] arr_dist = new int[n];

		//Integer.MAX VALUE. Set all nodes' distances to infinity.
		Arrays.fill(arr_dist, Integer.MAX_VALUE);

		//set the source node's distance to 0.
		arr_dist[search] = 0;

		while (!dq.isEmpty()) {
			Node curr = dq.pollFirst();
			int currVal = curr.getTheVal();
			int real_Weight = curr.getTheWeight();
			int currParent = curr.getTheParent();

			//If the destination node is found, we go back.
			if (currVal == end_dest)
				return real_Weight;

			//iterate through the current node's neighbours
			for (Node neighbour_Node: newAdj.get(currVal)) {
				int neighbour = neighbour_Node.getTheVal();
				if (neighbour == currParent)
					continue;

				int weight_total = neighbour_Node.getTheWeight();
				if (weight_total == 0 && arr_dist[neighbour] > real_Weight) {
					arr_dist[neighbour] = real_Weight;
					dq.offerFirst(new Node(neighbour, real_Weight, currVal));
				} else if (arr_dist[neighbour] > real_Weight + weight_total) {
					arr_dist[neighbour] = real_Weight + weight_total;
					dq.offerLast(new Node(neighbour, real_Weight + weight_total, currVal));
				}
			}
		}
		return Integer.MAX_VALUE;
	}

	private static List<List<Node>> biDirectionalGraphGet(List<List<Integer>> graph_adj) {
		int n = graph_adj.size();
		List<List<Node>> newAdj = new ArrayList<>();

		for (int i = 0; i<n; i++)
			newAdj.add(new ArrayList<>());

		boolean[] already_checked = new boolean[n];
		Queue<Integer> queue = new LinkedList<>();

		for (int i = 0; i<n; i++) {
			if (!already_checked[i]) {
				already_checked[i] = true;
				queue.offer(i);

				while (!queue.isEmpty()) {
					int curr = queue.poll();
					for (int neighbour: graph_adj.get(curr)) {

						//It is necessary to give the original edges a weight of 0.
						newAdj.get(curr).add(new Node(neighbour, 0));

						//Create a fictitious edge and give it a weight of 1.
						newAdj.get(neighbour).add(new Node(curr, 1));

						if (already_checked[neighbour]) {

							/*Don't put the neighbour's name back in the queue if they have already been visited.*/
							continue;
						}
						already_checked[neighbour] = true;
						queue.offer(neighbour);
					}
				}
			}
		}
		return newAdj;
	}
}

Output

2

Complexity

Time Complexity

O(V+E): where V is the number of vertexes and E is Edges.

Reason: As the current node's neighbours are iterated over while we check, create, and assign a fictional edge with a weight of one.

Space complexity

O(V+2*E): where V is the number of vertexes and E is Edges.

Reason: As in the worst-case scenario, we are using E space for each vertex. Hence the complexity of O(V+2*E).

Frequently Asked Questions

Can the shortest path be determined using BFS?

The shortest path in a weighted graph can only be found by BFS (or DFS) searching the complete graph and continuously keeping track of the shortest distance from the source to the destination vertex.

What does a graph's topological sort mean?

A topological sort or topological sorting of a directed graph in computer science is a linear arrangement of its vertices such that, for every directed edge uv from vertex u to vertex v, u occurs before v in the ordering.

Why is DFS used?

We can discover a path between two given vertices, u and v, using DFS. Topological sorting is a method used to schedule jobs based on their known dependencies on one. The DFS method may be used to do topological sorting. We can locate highly related graph elements using DFS.

Is the Floyd-Warshall algorithm greedy?

While the greedy algorithm evaluates each node passed to pick the shortest route (Local Optimum) so that the time needed for searching is faster, the Floyd-Warshall algorithm considers all potential routes so that some ways are presented. So it is regarded as a greedy algorithm.

What is an edge path?

A path in a network is a finite or infinite sequence of edges connecting a series of vertices that, by most definitions, are all distinct (and since the vertices are different, so are the edges).

Conclusion

We have gone through the Minimum edges to reverse to make path from a source to a destination and understand the solutions of it.
You should now fully understand how to use the graph and 0 1 BFS Concept. After reading this article from Coding Ninja.

Check Out these articles mentioned below.
 

• Graph
   
• 0 1 BFS Concept
   
• Learn Graphs
   
• Learn Trees
   
• Binary Tree
   
• Learn Trees (Hinglish).
   

If you face any doubt, please comment, and we will love to answer your questions.

• Recommended Problem - Reverse a Stack using Recursion
   

Want expertise in Python for your next web development project? Check out our course.
Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!