Find Minimum edges to reverse to make path from a source to a destination in C++
In this tutorial, we will see how to make a path from source to destination of a graph by reversing the minimum number of edges.
Consider a directed graph G with source node as 0(zero) and destination node as 6(six) as shown below.
In the above graph, there are two paths from source to destination,
Path A: 0 -> 1 -> 2 -> 3 -> 6
Path B: 0 -> 1 -> 4 -> 5 -> 6
In Path A only two edges need to be reversed in Graph G so that minimum edges reversed is only 2.
The above Graph is the result of reversing the edges to form a path from source to destination.
There is an alternate method of solving the problem. In this method, we make a reverse edge for every original edge and assign the weight 1 for reversed edge and 0 for the original edges. After applying this method the graph looks like,
Now we have altered the graph in such a way that, if we traverse towards the original edge the cost incurred is 0, but a cost of 1 will be added when moving towards the reversed edge. On applying Dijkstra’s shortest path on the graph will result in the minimum reversal of edges to reach from source to destination of the graph.
The complete program is given below:
#include <bits/stdc++.h> using namespace std; # define INF 0x3f3f3f3f class Graph { int Vrtx; // No. of vertices list< pair<int, int> > *adj; public: Graph(int Vrtx) // Constructor function { this->Vrtx = Vrtx; adj = new list< pair<int, int> >[Vrtx]; } void addEdges(int a, int b, int c) // Function that adds edge { adj[a].push_back(make_pair(b, c)); } vector<int> shortestPath(int src) // Function to return shortest path { set< pair<int, int> > setds; vector<int> dist(Vrtx, INF); //Create vector and initialise as //infinite setds.insert(make_pair(0, src)); //Insert source dist[src] = 0; while (!setds.empty()) { pair<int, int> tmp = *(setds.begin()); //Source vertex is min setds.erase(setds.begin()); //distance int a = tmp.second; // 'i' is used to get all adjacent vertices list< pair<int, int> >::iterator i; for (i = adj[a].begin(); i != adj[a].end(); ++i) { int b = (*i).first; // Get weight of current and adj vertex int weight = (*i).second; if (dist[b] > dist[a] + weight) //Check for shortest path { if (dist[b] != INF) setds.erase(setds.find(make_pair(dist[b], b))); dist[b] = dist[a] + weight; // Updating distance setds.insert(make_pair(dist[b], b)); } } } return dist; } }; //Function adds edge weight Graph EdgeWeight(int edge[][2], int E, int Vrtx) { Graph g(Vrtx); for (int i = 0; i < E; i++) { // original edge - weight 0 g.addEdges(edge[i][0], edge[i][1], 0); // reverse edge - weight 1 g.addEdges(edge[i][1], edge[i][0], 1); } return g; } int MinEdges(int edge[][2], int E, int Vrtx,int src, int dest) { Graph g = EdgeWeight(edge, E, Vrtx); // Gives modified graph // get shortes path vector vector<int> dist = g.shortestPath(src); if (dist[dest] == INF) // Not possible if infinite return -1; else return dist[dest]; // min no of edges } int main() //Main Function { int Vrtx = 7; int edge[][2] = {{0, 1}, {2, 1}, {2, 3}, {4, 1}, {5, 4}, {6, 5}, {6, 3}}; int E = sizeof(edge) / sizeof(edge[0]); int minimum = MinEdges(edge, E, Vrtx, 0, 6); if (minimum != -1) cout <<"Minimum number of edges to be reversed: " <<minimum; else cout << "Not possible"; return 0 ; }
OUTPUT
Based on our graph G, the minimum number of edges to be reversed to get the shortest path from source to destination is 2.
Output of the above program,
Minimum number of edges to be reversed: 2
We suggest you to further read the following:
Leave a Reply