Click here to Skip to main content
14,732,943 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I have an mXn matrix, starting from [0][0] cell I need to go to [m][n] through the lowest possible cost path, where costs are cell values (integer, greater than 0). Only moves possible are right, down and diagonally down.
I have tried Dynamic programming approach to find the lowest cost but could not be able to print the path.
e.g. for matrix {(3,2,8),(1,9,7),(0,5,2),(6,4,3)} its giving cost as 11, but as my approach converting the matrix to cost matrix, the path is printing wrong.

expected output:
cost: 11
path: B B D R (i.e. the traversal movements, Below, Down, Rigth)

The code attached here I have found in the internet. Please provide me snippet to print the path.

What I have tried:

public static int minimumCostPathDP(int[][] costMatrix, int m, int n) {
        int[][] minimumCostPath = new int[m+1][n+1];
        minimumCostPath[0][0] = costMatrix[0][0];
 
        for (int i = 1; i <= m; i++) {
            minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0];
        }
 
        for (int j = 1; j <= n; j++) {
            minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j];
        }
 
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                minimumCostPath[i][j] = costMatrix[i][j]
                                        + minimum(minimumCostPath[i - 1][j - 1],
                                                  minimumCostPath[i - 1][j],
                                                  minimumCostPath[i][j - 1]);
            }
        }
        return minimumCostPath[m][n];
    }
 
    public static int minimum(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
 
    public static void main(String[] args) {
        int[][] costMatrix = { { 3, 2, 8 }, { 1, 9, 7 }, { 0, 5, 2 }, {6, 4, 3} };
        System.out.println("Minimum cost: " + minimumCostPathDP(costMatrix, 3, 2));
    }
}
Posted
v2

This program is made to compute the minimum cost on a matrix, but nothing else.
This code have no provision to tell the minimum cost path, only its value.

I fear you will have to work a little and make a program that check every possible path until you find the one with minimum cost.

Nota: Java knows the length of arrays, in
public static int minimumCostPathDP(int[][] costMatrix, int m, int n)
, m and n can be deduced from costMatrix

Quote:
The code attached here I have found in the internet. Please provide me snippet to print the path.
Smell like HomeWork!
Looks like you are good at searching internet, now its time to work on your own.
   
If you would like fo find out how to print diagram, check this:
Dijkstra's shortest path algorithm in Java - Tutorial[^]
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm - Sanfoundry[^]
Feel fre to implement your own printing "diagram" method.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900