10.5

(a) Dijkstra-based solution
Model every cell (i,j) as a vertex whose cost is the value written in that cell. Add a directed edge from (i,j) to
  • (i+1,j) (move down) and
  • (i,j+1) (move right),
each edge weighted with the cost of the destination cell. Run Dijkstra from the source (0,0). The first time we extract vertex (s-1,t-1) from the priority queue we have the minimum-sum path.
Number of vertices V = s·t, number of edges E ≈ 2s·t. With a binary heap the running time is
[math]\displaystyle{ O(E\log V)=O(s\,t\,\log(s\,t)) }[/math].

(b) Dynamic-programming solution
Because edges go only right or down the graph is a DAG, so we can fill a table in top-to-bottom, left-to-right order:

dp[0][0] = grid[0][0] for i = 0 … s-1: for j = 0 … t-1: if i > 0 and j > 0: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) elif i > 0 : dp[i][j] = grid[i][j] + dp[i-1][j] # first column elif j > 0 : dp[i][j] = grid[i][j] + dp[i][j-1] # first row

The answer is dp[s-1][t-1] and the predecessor pointers (or a second pass) recover the path.
The table has s·t entries and each is computed in O(1), hence
[math]\displaystyle{ O(s\,t) }[/math] time and the same memory (or O(min(s,t)) with row/column rolling arrays).

Back to Chapter 10