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

112 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
``````

``````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

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
Similar Questions

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.

``````      40
/\
20 60
/\  \
10 30  80
/   /\
25  70 90
\
75

longest path
25 30 20 40 60 80 70 75
25 ----> 75
``````
``````                    10