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.

Find Minimum edges to reverse to make path from a source to a destination in C++

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.

Shortest path graph in C++

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,

Modified graph

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; 
    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 
    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; 
        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; 
        cout << "Not possible"; 
    return 0 ;


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

Your email address will not be published. Required fields are marked *