top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find the path with least sum between two zeros in a matrix?

+7 votes
509 views

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11      

0       16      23      31      16      7

67      5       4       23      21      19

Answer

1       6       8       9       0  ----> 3
                                         |
4       9       -5      5       11      13
                                         |
8       9       44      23      15      -20
                                         |
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11     
|
0       16      23      31      16        7

67      5       4       23      21       19
posted Nov 17, 2013 by Anuj Yadav

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

This is a direct application of bellman-ford algorithm
Note : This matrix must not contain negative weight cycle

First find 2 0's in the matrix and then apply Bellman-ford algo.

answer Nov 25, 2013 by Raghu
Similar Questions
+5 votes
String Path in Matrix ?

How to implement a function to check whether there is a path for a string in a matrix of characters? It moves to left, right, up and down in a matrix, and a cell for a movement. The path can start from any entry in a matrix. If a cell is occupied by a character of a string on the path, it cannot be occupied by another character again.

+5 votes
How to find nodes in a tree which has longest path? 
      40
      /\
     20 60
     /\  \
   10 30  80
      /   /\
     25  70 90
           \
           75

longest path 
25 30 20 40 60 80 70 75 
Answer
    25 ----> 75
+8 votes
Divide the array in two subarray such that difference of the sum is minimum?

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

+7 votes
Find the Common Ancestor and Print the Path. 
                    10
                    /  \                    
                   7     15
                  / \    / \
                 6   8  12  18
                /     \
               5       9
            (Given Binary tree)
...