Single pair shortest path in a matrix

Question

Let a MxN matrix where the start is at position (0,0) and the finish at (M-1,N-1) . Every square has a positive integer which is the cost to move on this square. What algorithm should I use for the shortest path from start to finish? We can recreate the problem using graphs. Where the squares are the vertices and the costs are weighted edges.

Example

Answer 1

Use Dijkstra. As soon as you hear "shortest path", look at Dijkstra. In particular, if you search for "dijkstra adjacency matrix" on stack overflow, you will get over a dozen questions discussing various aspects of how to apply Dijkstra on a graph represented as a matrix. You can build an adjacency matrix from your input matrix by looping through the input as follows:

create a (rows * cols) * (rows * cols) adjacency matrix       

for each square at position row,col in the input matrix
   let v = row*cols + col
   for all neighboring positions u (at row,col+1; row+1,col; and so on)
       set the cost of going from v to u to input[row][col]

You can even skip building the adjacency matrix, and simply calculate neighbors and distance-to-neighbors on the fly. This can save quite a lot of memory, at the expense of extra runtime.

You can also save some space by representing the graph as an adjacency list, but they are slightly more complicated to implement, and you seem to be just starting out.