Jun 122012
 

Given a Matrix of positive integers and 2 cells A & B. You have to reach from A to B covering cells such that the sum of elements in path is minimum. You can travel in forward, downward and diagonally. For example: If the given Matrix is as below:

 1 2 3 
 4 8 2  
 1 5 3

and you want to move from (0,0) to (2,2). Then you have to travel the following elements:

 1 2 3 
 4 8 2  
 1 5 3

Path: 1->2->2->3

Solution:

It is easy to visualize it recursively. If we start from the destination point and move backward. Then

Minimum Path to reach a point = Current Cell value + Minimum of paths from (top, left & top-left diagonal)

    /** Print the min sum path in a matrix. if the matrix is 
     * { {1, 2, 3},
     *   {4, 8, 2},
     *   {1, 5, 3} }
     *then path from (0,0) to (2,2) will be via 1->2->2->3
     *
     * (m,n) is the last cell where we want to reach.
     */
     int printMinPath(int arr[R][C], int m, int n)
     {

         if(m<0 || n<0)
            return POSOTIVE_INFINITY;

         if(n==0 && m==0)
            return arr[m][n]; // since array has only positive numbers
         else
         {
            int a = printMinPath(arr, m-1, n);
            int b = printMinPath(arr, m, n-1);
            int c = printMinPath(arr, m-1, n-1);
            return getMinimum(a, b, c) + arr[m][n];
         }
     }

Function getMinimum(int, int, int); is a simple function which accepts 3 int values and return the minimum of them.

  One Response to “Minimum path sum in a matrix”

Comments (1)
  1. What if the shortest path is a snake that ca go in all 8 directions?

    1 1 1 1 1 1 1 1 9 9 9 9 9 9
    0 0 0 0 0 0 0 1 0 0 0 0 0 9
    1 1 1 1 1 1 0 1 0 0 0 0 0 9
    1 0 0 0 0 1 0 1 0 0 0 0 0 9
    1 0 0 1 1 1 0 1 0 0 0 0 0 9
    1 0 0 1 0 0 0 1 0 0 0 0 0 9
    1 0 0 1 1 1 1 1 0 0 0 0 0 9
    1 0 0 0 0 0 0 0 0 0 0 0 0 9
    1 1 1 1 1 1 1 1 1 1 1 1 1 1
    your prgm will show only the 9 patn but not the ones path
    could you pls update the correct prgm bcos i really wanted it and google search got me here
    thank you.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)