Minimum Cost Path Problem in C++
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!
Leave a Reply