Minimum Cost Path Problem in C++

By Aniruddha Ghosh

Hello everyone! Today we will learn how to solve the Minimum Cost Path Problem in C++. At first, quickly see the problem statement. You are given an N*N grid in which every value represents the cost to traverse through that cell. You can move left, right, bottom, and up from any cell. Now you have to find a path from the top left corner to the bottom right corner such that the total cost incurred is minimum. You can see another similar problem here-Finding Minimum Cost Path in a 2-D Matrix in C++. But here constraints are different.

Minimum Cost Path Problem in C++ with Left, Right, Bottom and Up moves allowed

You can solve this problem by dynamic programming and graph algorithm concepts.

Now build the algorithm for this problem-

• At first, declare a 2D array named ‘dp’ for storing minimum cost for each cell and initialize it with INT_MAX. Then declare a visibility array named ‘vis’ for tracking if any cell is settled or not, and a min-heap to extract the minimum cost from all traversed cells. We can say any cell settled when the minimum cost is already found up to that cell.
• Then initialize the first cell of dp array with the top left corner value of input array and push it to min-heap.
• Now start extracting elements from min-heap and go to every adjacent of that cell(left, right, bottom and up) and push it to the heap if the current value of that adjacent is greater than the value of summation the popped element and the cost of that cell and the adjacent cell is not settled.
• You also have to extract the elements from the top of the heap if that cell is already settled.
• Do the steps until the heap becomes empty.

Now let’s see the program –

At first, declare the function getMinPath which get input array and its size as an argument

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll getMinPath(vector<vector<ll>>&arr,ll n){
//decalre a array for storing minimum cost up to that cell and initialize with INT_MAX
    vector<vector<ll>>dp(n,vector<ll>(n,INT_MAX));


//declare a visibility array to track setteled cells and initialize it with all false values
    vector<vector<bool>>vis(n,vector<bool>(n,false));
    typedef pair<ll,pair<ll,ll>> p;


//initialize dp[0][0] to the first cell of the input array
    dp[0][0]=arr[0][0];


//declare a mean heap 
    priority_queue<p,vector<p>,greater<p>>pq;
    ll i,j,val;
//push the first cell to the heap
    pq.push(make_pair(dp[0][0],make_pair(0,0)));


//start extracting from heap until the heap becomes empty
    while(!pq.empty()){
        auto temp=pq.top();
        pq.pop();
        i=temp.second.first,j=temp.second.second;
        val=temp.first;
        dp[i][j]=val;
        vis[i][j]=true;

//if the current cell is the bottom right then immediately return the value
        if(i==n-1 && j==n-1)
            return val;
    

//go to to left,right,bottom and up and push to the heap if criteria matched
        if(i-1>=0 && !vis[i-1][j] && dp[i][j]+arr[i-1][j]<dp[i-1][j]){
            dp[i-1][j]=dp[i][j]+arr[i-1][j];
            pq.push(make_pair(dp[i][j]+arr[i-1][j],make_pair(i-1,j)));
        }
        if(j-1>=0 && !vis[i][j-1] && dp[i][j]+arr[i][j-1]<dp[i][j-1]){
            dp[i][j-1]=dp[i][j]+arr[i][j-1];
            pq.push(make_pair(dp[i][j-1],make_pair(i,j-1)));
        }
        if(j+1<n && !vis[i][j+1] && dp[i][j]+arr[i][j+1]<dp[i][j+1]){
            dp[i][j+1]=dp[i][j]+arr[i][j+1];
            pq.push(make_pair(dp[i][j+1],make_pair(i,j+1)));
        }
        if(i+1<n && !vis[i+1][j] && dp[i][j]+arr[i+1][j]<dp[i+1][j]){
            dp[i+1][j]=dp[i][j]+arr[i+1][j];
            pq.push(make_pair(dp[i+1][j],make_pair(i+1,j)));
        }
            
//start popping the top elements if already settled
        if(!pq.empty()){
            temp=pq.top();
            i=temp.second.first,j=temp.second.second;
            while(!pq.empty() && vis[i][j]){
                pq.pop();
                if(!pq.empty()){
                temp=pq.top();
                i=temp.second.first,j=temp.second.second;}
            }
            
        }
    }
    return dp[n-1][n-1];
}

Then write the main function and from there call the getMinPath function-

//main function
int main()
{
//for fast input output
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//taking input from user
    ll n;
    cin>>n;
    vector<vector<ll>>arr(n,vector<ll>(n));
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++)
            cin>>arr[i][j];

    cout<<getMinPath(arr,n)<<'\n';

    return 0;
}

input:
5
31 100 65 12 18
10 13 47 157 6 
100 113 174 11 33 
88 124 41 20 140
99 32 111 41 20

output:327

I hope you understand the solution. Happy coding!