Determine shortest path in a 4x5 grid graph

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.

• 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). – Steven Nov 13 '19 at 8:24
• 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}$ – flutterbug98 Nov 13 '19 at 8:25
• 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). – Steven Nov 13 '19 at 8:30
• Would it matter if the edges could possibly have negative weights? – flutterbug98 Nov 13 '19 at 8:48
• 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. – Steven Nov 13 '19 at 9:15

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)$$.