Find shortest path with exactly k edges in a directed and weighted graph in C++

Given a directed and weighted graph, we have to find the shortest path between two vertices that have exactly k edges. In a directed graph, an edge only exists in one direction, i.e. from only one vertex to the other. Therefore a valid path is one that has k edges. Let’s take the following directed and weighted graph as the example for this tutorial:

For the above graph, there are 5 vertices and 8 edges. We’ll be taking vertex 0 and vertex 4 as the two vertices, and k=3 as an example question. The shortest path from 0 to 4 is 0->1->3->4 and the distance of this path is 7.

Approach

One by one we’ll traverse the neighbors of the source vertex looking for possible valid paths. After picking one of the neighbors, we’ll traverse neighbors of that neighbor until we reach the destination vertex with the edges in the path taken being k. After finding a valid path, we’ll compare it’s distance to the shortest path found until now. The easiest way to implement this approach is using recursion. Let’s take a look at the code and understand it better.

C++ program to find the shortest path with exactly k edges in a directed and weighted graph

#include <iostream>
#include <climits>
using namespace std;

int solve(int k,int s,int d,int v,int weights[5][5]){
    if(k==1&&weights[s][d]!=INT_MAX) return weights[s][d];    // Base cases of the recursive function
    if(k==0) return INT_MAX;
    
    int ans=INT_MAX;
    for(int i=0;i<v;i++){                                     //Traversing the neighbors
        if(weights[s][i]!=INT_MAX&&s!=i&&d!=i){               
            int temp=solve(k-1,i,d,v,weights);                   
            if(temp!=INT_MAX) {                               //if temp!=INT_MAX, then a valid path
                ans=min(ans,weights[s][i]+temp);              // from this neighbor exists
            }
        }
         
    }
    return ans;
}


int main(){
    int e;
    cin>>e;
    int v=5;
    int weights[5][5];
    for(int i=0;i<v;i++){
        for(int j=0;j<v;j++){
            if(i==j) weights[i][j]=0;     //Inititializing the elements of the adjacency matrix
            else weights[i][j]=INT_MAX;    
        }
    }
    for(int i=0;i<e;i++){
        int v1,v2,wi;
        cin>>v1>>v2>>wi;                  //Taking input for the edges and filling in the matrix
        weights[v1][v2]=wi;
    }
    int s,d,k;
    cin>>s>>d>>k;
    cout<<solve(k,s,d,v,weights)<<endl;
    
    
        
    return 0;
}

We take the input for the weighted and directed graph in the form of an adjacency matrix. The solve() function has two base cases. If only one edge is left and an edge between the current vertex and the destination vertex exists, this means that a valid path exists and it returns the distance of the last edge. Otherwise, if k reaches zero, it returns INT_MAX, as a valid path doesn’t exist in this case. This function iterates through the neighbors of the current vertex and checks if a valid path from that neighbor exists, and if it does, it compares its distance to the shortest path found until then. Therefore, by the end of the recursive calls, we have the shortest path with k edges.

Input

5
0 1 4
0 2 6
1 2 2
1 3 2
1 4 5
2 3 3
2 4 3
3 4 1

Output

7

C++ program to find next Smaller of next Greater in an array