CODEWITHSUNDEEP
algorithmdynamic-programmingshortest-path
roxrook
roxrook

Reputation: 13853

How to solve terrain map shortest path with dynamic programming?

Given a matrix of all positive integers, starting from the left most column 0th, find the minimum path to the right most column (n - 1)th. For example:
enter image description here

The minimum path is the path which contains on 1's.

At any given square m[i, j], we can move to 4 directions (left, right, up, down); of course except all corner cases at left most, right most row/column. For example, at [0, 0], we only can move right or down.
My solution is to build a graph of m x n vertices, then run Floyd-Warshall to compute all pair shortest path of any two vertices (u, v). Then run another nested for loop to check all the vertices of the 0th column with all vertices of the (n - 1)th column to find the minimum path.
However, my professor suggested another algorithm by using the following recurrence:

S[i, j, L] = 
    min(
        S[i - 1, j, L - 1] + cost[i - 1, j],
        S[i + 1, j, L - 1] + cost[i + 1, j],
        S[i, j - 1, L - 1] + cost[i, j - 1],
        S[i, j + 1, L - 1] + cost[i, j + 1]);

which I have no clue how it works! Since at any given square [i, j] we can move in 4 direction and this make it impossible to build a table based on previous pre-computed values.
Did I miss something here? I can't see how this recurrence work out. Any idea?

Upvotes: 1

Views: 1879

Answers (1)

Vaughn Cato
Vaughn Cato

Reputation: 64308

If you have S[i,j,0] = infinity, except for S[0,j,L] = 0, then it should work. Eventually all S[i,j,L]==S[i,j,L+1] and you can stop iterating. S[i,j,L] then has the cost of the shortest path from the first column to that cell.

This is how this recurrence would look in the upper-left corner for increasing values of L.

0   inf inf inf inf
0   inf inf inf inf
0   inf inf inf inf

0   1   inf inf inf inf
0   20  inf inf inf inf
0   21  inf inf inf inf

0   1   2   inf inf inf
0   2   30  inf inf inf
0   21  22  inf inf inf

0   1   2   3   inf inf
0   2   3   39  inf inf
0   12  22  23  inf inf

0   1   2   3   4   inf
0   2   3   4   47  inf
0   12  12  23  24  inf

0   1   2   3   4   5  
0   2   3   4   5   48  
0   12  12  12  24  25 

0   1   2   3   4   5  
0   2   3   4   5   6   
0   12  12  12  6   25 

0   1   2   3   4   5
0   2   3   4   5   6
0   12  12  7   6   7

0   1   2   3   4   5
0   2   3   4   5   6
0   12  8   7   6   7

0   1   2   3   4   5
0   2   3   4   5   6
0   9   8   7   6   7

No further changes will take place in the upper-left corner. You can see that it is slowly discovering the minimum cost to reach each cell.

Upvotes: 4

Related Questions