Figure $1$: Graph for Question $6$

$6\mathrm{.}1)$ Draw the subproblem graph for finding the shortest path from s

to t in Figure $1$ using the dynamic programming formulation $\backslash$delta $($s$,$ t$)=$ min$\_($w in N$($s$))\backslash$delta $($s$,$w$)+$weight$($w$,$ t$)$ where N$($s$)$ denotes the out$-$neighborhood of s $($that is all the vertices u for which s $->$ u is an edge in the graph$)$

$6\mathrm{.}2)$ Argue that in the following dynamic programming formulation for

computing the shortest path $($which takes edges on the path as an extra paramter$)$ there are no cyclic dependencies in the subproblem graph.

$\backslash$delta k$($s$,$ t$)=$ min w for which w$->$t in E$($G$)\backslash$delta $\_($k$1)($s$,$w$)+$ weight$($w $->$t$)$

Here $\backslash$delta k$($a$,$ b$)$ denotes the shortest path from a to b using at most k edges.Question $6$

Question $6\mathrm{.}1(3$ points$)$ Draw the subproblem graph for finding the shortest path from $s$

to $t$ in Figure $1$ using the dynamic programming formulation $(s,t)=mi{n}_{\text{w}\text{i}\text{n}\text{N}(s)}(s,w)+$

weight $(w,t)$ where $N(s)$ denotes the out$-$neighborhood of $s($that is all the vertices $u$ for

which $su$ is an edge in the graph$)$

Question $6\mathrm{.}2(4$ points$)$ Argue that in the following dynamic programming formulation for

computing the shortest path $($which takes edges on the path as an extra paramter$)$ there are

no cyclic dependencies in the subproblem graph.

${}_k(s,t)=mi{n}_{w\text{f}\text{o}\text{r}\text{w}\text{h}\text{i}\text{c}\text{h}w\text{t}\text{i}\text{n}\text{E}(G)}{}_{k-1}(s,w)+$ weight $(wt)$

Here ${}_k(a,b)$ denotes the shortest path from $a$ to $b$ using at most $k$ edges.