C program for minimum cost path

Here we will solve the minimum cost path problem in C language. This is meant to be done on a 2D matrix where each cell has a movement cost. We must find a path from the upper left corner to the lower right corner with the minimum travel cost. You can only traverse cells down and to the right from a given cell.

To solve this specific problem, dynamic programming is better than recursion.

Given the cost matrixc ost[ ][ ] and the position (m,n), we must write a function that returns the arrival from (0,0) Minimum path cost from (m,n) The total cost of a path to (m,n) is the sum of all costs on that path (including source and destination).

Assumption− All costs are positive. There is no negative cost cycle in the input matrix

Example

Find the minimum cost path to (2,2)

The cost is in the image given in itself. The path will be (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2). The path has a value of 8 (1 2 2 3).

Method− Creates an answer matrix similar in size to the given matrix.

Populate this matrix in a bottom-up fashion.

Given− arrA[ ][ ]. In each cell we have 2 options (right or down) and for any i,j cell we can choose the minimum of these 2 options.

solution[i][j]=A[0][j] if i=0, 1st row
   =A[i][0] if j=0, 1st column
=A[i][j]+Min(solution[i=1],[j],solution[i][j-1]) if i>0 && j>0

The approach followed in the algorithm answer can solve this problem efficiently by applying dynamic programming. Create a minimum cost path table of size m,n and define -

minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)

Obviously,

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero
minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero

Next, we will fill the minimum cost path matrix by applying similar formulas as applied in the algorithm . Since all previous values ​​have been calculated within the minimum cost path matrix, we do not recalculate these values ​​as in the algorithm answer.

minimumCostPath[i][j] = costMatrix[i][j] +minimum(minimumCostPath[i - 1][j - 1],minimumCostPath[i - 1][j],minimumCostPath[i][j - 1])

Here, in order to calculate minimumCostPath[i][j], we tend to use minimumCostPath[i - 1][j - 1], minimumCostPath[i - 1][j] and minimumCostPath[i][ j - 1] As a result, these are the only allowed cells where we reach minimumCostPath[i][j]. Finally, we return minimumCostPath[m][n].

The time complexity of the dynamic programming algorithm is O(mn).

Example

Real-time demonstration

#include <iostream>
using namespace std;
int min_(int a, int b, int c){
   if (a < b)
      return (a < c) ? a : c;
   else
      return (b < c) ? b : c;
}
int min_cost(int cost[4][4], int m, int n){
   int i, j;
   int tot_cost[4][4];
   tot_cost[0][0] = cost[0][0];
   for (i = 1; i <= m; i++)
   tot_cost[i][0] = tot_cost[i - 1][0] + cost[i][0];
   for (j = 1; j <= n; j++)
      tot_cost[0][j] = tot_cost[0][j - 1] + cost[0][j];
   for (i = 1; i <= m; i++)
      for (j = 1; j <= n; j++)
         tot_cost[i][j] = min_(tot_cost[i - 1][j - 1], tot_cost[i - 1][j], tot_cost[i][j - 1]) + cost[i][j];
      return tot_cost[m][n];
}
int main(){
   int cost[4][4] = {
      { 9, 9, 4 },
      { 8, 0, 9 },
      {1, 2, 8}
   };
   cout<<" The minimum cost is "<<min_cost(cost, 2, 2);
   return 0;
}

Output

The minimum cost is 17

The above is the detailed content of C program for minimum cost path. For more information, please follow other related articles on the PHP Chinese website!