DP: Shortest path algorithms

PDF of Eric’s handwritten notes are here.

Shortest path algorithms using DP

Input: Directed $G=(V,E)$ with edge weights $w(e)$ .

Fix $s\in V$ : Dijkstra’s algorithm finds for all $z\in V$ , $dist(z)=$ length of shortest path from $s$ to $z$ in time $O((n+m)\log n), n=|V|, m=|E|$ , assuming all edge weights are non-negative.

What if negative weight edges? May be negative weight cycles (see example in handwritten notes). Assume no negative weight cycles for now (see how to deal with them later.)

Solve using DP. Note: for shortest path $P$ from $s$ to $z$ , $P$ visits every vertex at most once if no negative weight cycle.So $P$ is of length $\le n-1$ edges.

DP idea: use $i=0\rightarrow n-1$ edges on the path.
For $0\le i\le n-1$ , and $z\in V$ ,
let $D(i,z)=$ length of shortest path from $s$ to $z$ using $\le i$ edges.

Base case: $D(0,s)=0$ ,
and for $z\neq s$ : $D(0,z)=\infty$ .

For $i\ge 1$ : look at a shortest path $P$ from $s$ to $z$ using $\leq i$ edges.
Thus, $D(i,z)=\min\{ D(i-1,z),\min_y\{D(i-1,y)+w(y,z)\}\}$ .

Pseudocode:

$Bellman-Ford(G,s,w)$ :

for all $z\in V$ , $D(0,z)=\infty$
$D(0,s)=0$
for
- for all $z\in V, D(i,z)=D(i-1,z)$
- for all :
  - if $D(i,z)>D(i-1,y)+w(y,z)$ , then $D(i,z)=D(i-1,y)+w(y,z)$
Return $D(n-1,\cdot)$

Running time: $O(nm)$ .

How to find a negative weight cycle?
Check if $D(n,z)< D(n-1,z)$ for some $z\in V$ .

Now what if we want all-pairs shortest paths? Then if we run Bellman-Ford $n$ times, we get a $O(n^2m)$ time algorithm.

Better approach: using dynamic programming.

Let $dist(v,z)=$ length of shortest path from $v$ to $z$ .

Do we condition on the number of edges as in Bellman-Ford? This will give an $O(n^2m)$ time algorithm), is there a better approach?
Instead we will condition on the set of intermediate vertices.

Idea: Arbitrarily order the vertices, so $V=\{v_1,v_2,\dots,v_n\}$ .
For $0\le i\le n$ and $v,z\in V$ ,
let $D(i,v,z)=$ length of shortest path from $v$ to $z$ using a subset of $\{v_1,\dots,v_i\}$ as intermediate vertices.

Base case:

$D(0,v,z)= \begin{cases} w(v,z) & \mbox{ if } (v,z)\in E \\ \infty & \mbox{ if } (v,z)\not\in E. \end{cases}$

Recurrence: look at $D(i,y,z)$ for $i\ge 1$ : (assuming no negative weight cycle)

if $v_i$ is not used, then $D(i,y,z)=D(i-1,v,z)$
if $v_i$ is used, then the path goes through $v_i$ and so it can be broken into two parts: a path from $y$ to $v_i$ and $v_i$ to $z$ (see the handwritten notes for an illustration).

Hence, for $i\ge 1$ and vertices $y,z\in V$ :
$D(i,y,z)=\min\{D(i-1,y,z), D(i-1,y,v_i) + D(i-1, v_i, z)\}$ .

Pseudocode:

$Floyd-Warshall (G,w)$ :

For all :
- for all :
  - if ,
    - then $D(0,y,z)=w(y,z)$
    - else $D(0,y,z)=\infty$
For
- for all
  - for all
    - $D(i,y,z)=\min\{D(i-1,y,v_i)+D(i-1,v_i,z),D(i-1,y,z)\}$
Return $D(n, \cdot, \cdot)$

Running time is $O(n^3)$ .

How do we check for a negative-weight cycle?
Check if $D(n,y,y)<0$ for some $y\in V$ .

Algorithms

Lecture videos+notes

DP: Shortest path algorithms