$(24$ points$)2.$ The Bellman$-$Ford algorithm is a dynamic program approach in nature to solve the

single$-$destination shortest$-$paths problem: given a graph $G(V,E_{{?}_{?}})$ with a weight $w(e)$ associated

with each edge inE, find the shortest path to a given destination vertex inV from every other

vertex inV.

Hint: reference to Section $22\mathrm{.}1$ in the textbook

$(5$ points$)2\mathrm{.}1$ Let's use OPTvinV to denote the minimum weight of a $v-t$

path using at most i edges. Represent the optimal value OPT$(i,v)$ initially and recursively.

$(5$ points$)2\mathrm{.}2$ Describe a dynamic programming algorithm in pseudocode to identify the optimal

solution.

$(11$ points$)2\mathrm{.}3$ Write down the two$-$dimensional dynamic programming table of optimal values

with tracking arrows for the following example problem instance.

$(3$ points$)2\mathrm{.}4$ List the lowest$-$cost paths from vertex $d$ to vertex $t.$