CODEWITHSUNDEEP
c++matrixdynamic-programming
JKLM
JKLM

Reputation: 1520

Print path with minimum sum among all the possible paths in matrix using dynamic programming

I want to print the minimum sum of the matrix where you are allowed to move either right or down. I'm able to get cost but I'm not sure how can I print path with the minimum sum among all the possible paths.

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;

    #define M 3
    #define N 3

    int findMinCost(int cost[M][N])
    {
        int T[M][N];

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                T[i][j] = cost[i][j];

                if (i == 0 && j > 0)
                    T[0][j] += T[0][j - 1];

                else if (j == 0 && i > 0)
                    T[i][0] += T[i - 1][0];

                else if (i > 0 && j > 0)
                    T[i][j] += min(T[i - 1][j], T[i][j - 1]);

            }
        }

        return T[M - 1][N - 1];
    }

    int main()
    {
        int cost[M][N] =
        {
            { 9,-2,10 },
            { 15,23,-10 },
            { 40,16,2 },
        };

        cout << "The minimum cost is " << findMinCost(cost);

        return 0;
    }

Upvotes: 0

Views: 1109

Answers (1)

Mukul Gupta
Mukul Gupta

Reputation: 2425

You can use another 2-d array of std::pair to store the indexes of the path taken to reach the optimal solution.

Reconstructing the solution

  1. For reconstructing the solution, declare path to store the last path taken to arrive at the optimal solution.

std::pair<int,int> path[M][N]

  1. In your inner loop, everytime T[i][j] is computed, also compute path[i][j]

    if (i == 0 && j > 0) {
  T[0][j] += T[0][j - 1];
  path[0][j] = std::make_pair(0, j - 1);
}
else if (j == 0 && i > 0) {
  T[i][0] += T[i - 1][0];
  path[i][0] = std::make_pair(i - 1, 0);
}
else if (i > 0 && j > 0) {
  if (T[i - 1][j] < T[i][j - 1]) {
    T[i][j] += T[i - 1][j];
    path[i][j] = std::make_pair(i - 1, j);
  } else {
    T[i][j] += T[i][j - 1];
    path[i][j] = std::make_pair(i, j - 1);
  }
}

  2. Finally, using the path array reconstruct the solution using a recursive function as follows (it can also be converted to an iterative solution)

    void printPath(int i, int j, std::pair<int,int> path[M][N], int cost[M][N])
{
  if (!i && !j) {
    cout << cost[i][j] << ' ';
    return;
  }
  printPath(path[i][j].first, path[i][j].second, path, cost);
  cout << cost[i][j] << ' ';
}

Demo: here

Upvotes: 2

Related Questions