# Feb 11. Dynamic Programming

Shortest s-t path: Given graph $G = (V, E)$ and $l(i,j)$ is the length of the direct edge between $i$ and $j$, we wish to compute a shortest path from $s$ to $t$. We assume that $l(i, j) \ge 0$ for every $i, j \in V$.

Consider the following algorithm (Dijkstra) for shortest paths.

• Initialize $S = \{s\}$
• Assign tentative distances $T$ to every vertex as $T(s) = 0$, $T(v) = l(s, v)$ if $(s,v)\in E$ and otherwise $T(v) = \infty$.
• Let $v$ be the vertex with smallest $T(v)$.
• For every neighbor $u$ of $v$, if $T(u) > T(v) + l(v, u)$ then update $T(u) = T(v) + l(v, u)$.
• Add $v$ to $S$ and iterate till $S = V$.

Lemma: Every time we add a vertex $v$ with the smallest $T(v)$ then $T(v) = d(v)$ where $d(v)$ is the actual shortest path length from $s$ to $v$.

Proof: Consider a shortest $s$ to $v$ path $P$ and assume for the sake of contradiction that $|P| < T(v)$. Since $v \notin S$, it must leave $S$ at some vertex $w$. Let $w'$ be the vertex immediately before $w$ in $P$ (hence $w' \in S$). By induction $T(w') = d(w')$ and when we included $w'$ in $S$ we must have relaxed $w$ so that $T(w) \le T(w') + l(w',w)=d(w') + l(w', w)$. Since $T(w) \le d(w') + l(w', w) \le |P| < T(v)$, we arrive at a contradiction.

Running Time: The iteration runs for $n$ times (since it stops only when $S = V$). Inside the loop we only look at an edge once – once we update a vertex using that edge we never use it to update that same vertex again. To find the vertex with the shortest $T(v)$ we can use a min-heap and then the run time is $O(n\log{n} + m)$.

Variant of the problem

Suppose we want to find a shortest path between $s$ and $t$ that uses at most $j$ edges. Let $P(a, b, j)$ be defined as the shortest path from $a$ to $b$ using at most $j$ edges. We claim that $P(a, b, j) = \min\{ P(a, b, j-1), P(a, c, j-1) + l(c, b)\}$. This is because the optimal path from $a$ to $b$ using at most $j$ edges could either use atmost $j-1$ edges or it must have used at most $j-1$ edges to go from $a$ to $c$ for some $c$ and then used the edge $(c, b)$.

How do we turn this into an algorithm? Consider a table $A$ whose rows are indexed by pairs $(a, b)$ of vertices and the columns are indexed by $\{1, 2, 3, \cdots, j\}$. The entry $A[(a,b)][i]$ corresponds to the shortest $a$ to $b$ path using at most $i$ edges. Note that we can fill the first column trivially: $A[(a,b)][1] = l(a,b)$. Suppose we have inductively filled up the first $i-1$ columns. To fill the $i^{th}$ column we simply use the formula $A[(a,b)][i]=\min\{A[(a,b)][i-1], A[(a,c)][i-1]\}$. Note that since column $i-1$ was already filled, all the values $A[(a,c)][i-1]$ are available to us. The run time of this algorithm is $O(n^2j)$.

All Pairs Shortest Path

Let $P(i, j, k)$ be the shortest path from $i$ to $j$ using vertices $\{1, 2, 3, \cdots, k\}$. Then we can write $P(i, j, k) = \min\{ P(i, j, k-1), P(i, k, k-1) + P(k, j, k-1)\}$. One can convert this into a table filling algorithm with running time $\Theta(n^3)$.