1
$\begingroup$

I need to find the minimal path cost from left edge of a $n\times n$ grid to the right edge where each node has some non-negative weight $cost(i,j)$. $i$ represents horizontal coordinates while $j$ represents vertical coordinates. Only the following movements are allowed in the grid: $$ (i,j)\to(i+1, j-1) \quad\text{aka diagonal down}\\ (i,j)\to(i+1, j) \quad\text{aka right}\\ (i,j)\to(i+1, j+1) \quad\text{aka diagonal up}\ $$ The algorithm must run in $\Theta(n^2)$ time and use dynamic programming.

I thought:

1) first to select the minimal cost node in the left-most column, that is find $min(cost(i, 1))$. Let the node be $s$ (start node).

2) Now we can use Bellman-Ford algorithm as described here (page 53) in order to find the minimal cost path from $s$ to any other node. The recurrence for Bellman-Ford would be: $$ opt(i,j) = cost(i,j) + min(opt(i+1,j-1),\\ opt(i+1, j),\\ opt(i+1,j+1)) $$

3) We'd get a $n\times n$ matrix in the end where the right-most column would represent the right-most edge of the grid. Therefore the minimal cost path from left edge to the right edge would be the minimal cost in the right column.


Is my logic on the right track? I'm really not sure regarding the steps 1) and 3). Also because Bellman-Ford calculates edges costs do I need to perform any reduction in this algorithm because costs are not stored on edges but rather on nodes?

$\endgroup$
  • $\begingroup$ Are you sure that $(i,j)\to (i+1,j)$ is right? shouldn't be "down"? $\endgroup$ – Nehorai Dec 27 '17 at 12:28
  • $\begingroup$ @Nehorai yes, $i$ symbolizes horizontal movement so if $j$ doesn't change then we move to the right because $i$ increases $\endgroup$ – Yos Dec 27 '17 at 13:06
  • $\begingroup$ but $i$ is the rows indexes not columns so $(i,j)→(i+1,j)$ is down, no? $\endgroup$ – Nehorai Dec 27 '17 at 13:10
  • $\begingroup$ @Nehorai No $i$ represents columns $\endgroup$ – Yos Dec 27 '17 at 13:12
  • $\begingroup$ No, see here for example @Yos $\endgroup$ – Nehorai Dec 27 '17 at 13:14
1
$\begingroup$

You can solve this problem filling the following table.

Let's say that $cost(row,col)$ is the minimal cost that can be achieved starting from one node on the leftmost edge of the grid and ending in the cell $(row, col)$, only performing valid operations.

The answer to the problem will be the minimum among all $cost(i,j)$ where $j=last\_col$. Notice that table $cost$ table is the same as $opt$ table, but now you have the proper semantic of it's entries, so it's easy to fill base values, and extract final values.

  • Step 1: Base values: Fill first column entries with there current value. i.e $cost(i,j)$ where $j=0$. It is $cost(i,0)=value(i,0)$ since the only way you can reach node $(i,0)$ starting in a leftmost node and performing valid operation, is starting in the node itself.
  • Step 2: The same you described before. This holds, because you can only get nodes on the $j^{th}$ column from the $(j-1)^{th}$ column, and since you are filling $cost$ table in increasing order of columns, previous values will be computed when you need to compute current values. [This is dynamic programming]
  • Step 3: As I said before, and you said too, return the minimal value among all entries in the last column of $cost$ table.

Why Bellman Ford (BF) works here in the way you do it.

BF algorithm finds shortest path in a graph from a single source to every other node inside the graph. In the $k^{th}$ step BF have already computed shortest path starting from source node $S$ to every other node using at most $k$ edges.

Let's transform our problem into a valid instance for BF, and the let's modify BF to run in $O(n^2)$.

Let's say we convert each cell of the grid into a node, and you put an edge between node $u$ and $v$ if the transition from $u$ and $v$ is valid. Let the cost of edge between $u-v$ be the original cost of the cell $v$, so moving through this edge adds to the overall cost getting into node $v$, as we expect.

Now we have two problems.

  • Problem 1, the running time of our algorithm will be $O(nodes \cdot edges)$ where $nodes$ is $n^2$ and $edges$ is $O(nodes) = O(n^2)$ so overall complexity will be $O(n^4)$.
  • Problem 2. There are several sources, so we need to run BF starting at every source, and this increase the overall complexity by a factor of $n$.

Let's get rid of both problems, starting from problem 2. If you add an extra node connected to every node at the first column, you simulate the process of starting at every node in one run. Look at the following image for more understanding. I didn't pain all connection but just a few. enter image description here

To get rid of the first problem, you need to exploit the structure of our graph. It is not so general. You can only reach nodes in the $k^{th}$ column in the $k^{th}$ step, and since there is no backward edge, in this step only nodes in this column needs to be updated. So overall complexity will be $O(nodes) = O(n^2)$.

$\endgroup$
  • 1
    $\begingroup$ @Yos yes, using Bellman-Ford algorithm! Notice that BF algo find after step $k$ all shortest path from source to each node using at most $k$ edges. Here you know that using $k$ edges you can reach up to the $k^{th}$ column, so you don't have to update any further column. $\endgroup$ – Marcelo Fornet Dec 27 '17 at 16:11
  • 1
    $\begingroup$ Excellent question! This problem is in several ways different from the problem BF solve. Here you have multiple source and cost on nodes instead of edges. So, you can add an extra node, and connect it to all nodes on the first column and instead of letting the cost being in the nodes put them on the edges that enter each node. Then you can find shortest path starting from this extra node. You don't really need to do that in the implementation. $\endgroup$ – Marcelo Fornet Dec 27 '17 at 16:17
  • 1
    $\begingroup$ let me illustrate the way it works in my answer $\endgroup$ – Marcelo Fornet Dec 27 '17 at 16:23
  • 1
    $\begingroup$ @Yos I already extended my answer, in order to make it clear for you. $\endgroup$ – Marcelo Fornet Dec 27 '17 at 16:46
  • 1
    $\begingroup$ @Yos notice that $n$ in BF is for nodes. So complexity is $O(nodes \cdot edges)$ in BF. We have $nodes=n^2$. $\endgroup$ – Marcelo Fornet Dec 28 '17 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.