Bellman-Ford Algorithm

Bellman-Ford, like # Dijkstra's Algorithm, is also a algorithm to find a shortest path in a graph.

If $G$ has no negative cycles, then there is a shortest path from $s$ to $t$ that is simple (i.e., does not repeat nodes), and hence has at most $n-1$ edges.

Let $OPT(i,v)$ to denote the minimum cost of a $v-t$ path using at most $i$ edges. Our problem is to compute $OPT(n-1,s)$.