Posted by: atri | December 9, 2009

## Lect 38: Shortest Paths-II

(Guest post by John Longanecker)

The last several classes we have been learning about dynamic programming. Richard Bellman was the one who created dynamic programming.  I find it interesting to read up on people we have talked about in class. So go check him out.

The basic goal of dynamic programming is to solve a bunch of smaller problems and assemble the results to find the solution of a larger problem. To compute a problem quickly we do not compute already computed problems. An example of this is to how we used an array to help us with the weighted interval scheduling problem.

The problem that we worked on solving in today’s lecture was the shortest path problem using dynamic programming (6.8). We are given a graph $G$ and asked to find the shortest path between two nodes $s$ and $t$. It is also important to note that we are not going to use graphs with negative cycles.  Negative cycles brings up a whole other problem and we want to focus on the case of a graph $G$ with no negative cycles.
In order to calculate this problem we took a function $OPT(i,v)$ = the shortest path from node $v$ to $t$ using at most $i$ edges.  For example adding more edges does not necessarily mean the path will be longer. We could have negative weight edges or the route with more edges could have a smaller set of edge weights.

Lemma:
If $G$ has no negative cycle, there is a shortest path has no repeated vertices.

This implies there is a shortest path with at most $n-1$ edges.

We constructed a table where the rows represented the nodes we are starting at and the columns represented the maximum allowed number of edges ($i$) used to traverse from the starting node $v$ to $t$ using at most $i$ edges. Each cell will be populated with value $OPT(i,v)$ returns.  If we look at the highest value of $n-1$ (most number of edges) we will always find the optimal value of the shortest path for the particular node we are interested in.
Shortest path is not simple (it has a cycle) we will call it $P_1$. By assumption the cycle is not negative (it has to be at least  $0$)
Contradiction: So that being said we could remove the cycle from the path $P_1$ so that we have a new path $P_2$.
$\mathrm{cost}(P_2) \le \mathrm{cost} P_1$ it will never be larger (because we already decided that there will be no negative cycles in $G$).
If the shortest path uses only $i-1$ edges, $OPT(i,v)$ will still return the optimal path weight, but it will not be any smaller then $i-1$.