Consider a directed graph G with a positive weight w$($e$)$ assigned to each edge

e in E$($G$)$ where vertices are arranged on a rectangular grid such that vertices are labeled as

V $($G$)=\{$vi$,$j $|1<=$ i$,$ j $<=$ k$\}$

See an example G shown in Figure $1$ where k $=4$ and n $=16.$ We are interested in finding

Figure $1$: G

a shortest path from v$1,1$ to vk$,$k$.$ We can certainly apply the Dijkstra$$s algorithm to find a

shortest path in O$($n

$2$

$)$ time where k

$2=$ n$.$ Note that the Dijkstra$$s algorithm works for any

arbitrary graph. However, each vertex in G has at most two incoming edges.

Design your own algorithm that compute a shortest path from v$1,1$ to vk$,$k in O$($n$)$ time.