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:

• Dijkstra’s shortest path algorithm in C++
• Graph Representation – Adjacency List in C++