minimum path from top left to bottom right cell, where we can traverse in north, south, east, west directions

Question

How to find minimum path from top left to bottom right cell in a 2D-matrix with costs where we can traverse in north, south, east, west directions.

Answer 1

If the cost values are constrained to be nonnegative, the problem can be solved by Dijkstra's shortest path algorithm. Otherwise, the problem is not well-defined since cycles of negative length occur. To be more specific, the weight for an edge from cell A to B is set to be the weight of A; the weight of the terminal cell in the bottom right corner is included in every path.