1
$\begingroup$

Suppose we had a graph $G = (V,E)$.

This graph can also be seen as a $4x5$ grid graph as shown in the image.

There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and $1 \leq j \leq m-1$.

Similarly, there is a directed edge from $v_{i,j} \rightarrow v_{i+1,j}$ for $1 \leq i \leq n-1$ and $1 \leq j \leq m$.

What is the most efficient algorithm to determine the shortest path from $v_{1,1} \rightarrow v_{n,m}$? My main idea is to use the Bellman-Ford algorithm, but I am clearly not taking advantage of how this graph is laid out. Any guidance would be much appreciated.

EDIT: The edges are weighted and may possibly be negative.

enter image description here

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ To find a shortest path from $v_{i,j}$ to $v_{h,k}$ in this particular graph (assuming $h \ge i$ and $k \ge j$, otherwise there is no directed path) you can pick any path that uses a vertical edge $h-i$ times and an horizontal edge $k-j$ times. E.g., the one going from $v_{i,j}$, to $v_{h,j}$, to $v_{h,k}$. Clearly this can be done in constant time if you are fine with just the distance or with a compact description of the path. Otherwise you can explicitly report the path's edges in time proportional to the path's length (which is constant anyway since this is at most $7$ in this graph). $\endgroup$
    – Steven
    Nov 13, 2019 at 8:24
  • $\begingroup$ I apologize, I forgot to mention that we are trying to determine the most efficient way to find the shortest path from $v_{1,1} \rightarrow v_{n,m}$ $\endgroup$
    – flutterbug98
    Nov 13, 2019 at 8:25
  • 1
    $\begingroup$ All the considerations of my previous comment still apply. If you don't have the vertices labelled as in the figure, and you're just given the id of $v_{1,1}$ then you can just use a DFS search from $v_{1,1}$. You'll reach a sink in $7$ (in general $n+m-2$) steps and that'll be exactly $v_{4,5}$ (in general $v_{n,m})$. (Notice also that each traversed vertex takes a constant time to process). $\endgroup$
    – Steven
    Nov 13, 2019 at 8:30
  • $\begingroup$ Would it matter if the edges could possibly have negative weights? $\endgroup$
    – flutterbug98
    Nov 13, 2019 at 8:48
  • $\begingroup$ It would. In fact it matters even if there are non-negative weights. Since the graph is a DAG you can solve your problem with possibly negative weights in $O(|V|+|E|) = O(|V|)$ time by using dynamic programming. $\endgroup$
    – Steven
    Nov 13, 2019 at 9:15

1 Answer 1

Reset to default
3
$\begingroup$

Since your graph is a DAG you can topologically sort $V$ and solve your problem via dynamic programming by considering the vertices in reverse topological order.

For each vertex $v$, let $d(v)$ be the distance from $v$ to $v_{n,m}$. Clearly, if $v = v_{n,m}$, then $d(v)=0$.

For $v \neq v_{n,m}$, you have: $$ d(v) = \min_{(v,u) \in E} \{ w(v,u) + d(u) \}, $$

where $w(v,u) \in \mathbb{R}$ is the weight of edge $(v,u)$ in $G$.

Both the topological order of $V$ and all the quantities $d(v)$ can be found in $O(|E|)$ time. Therefore the overall time required is $O(|E|) = O(|V|) = O(nm)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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