DP Part III

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 positive.

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 i=1\rightarrow n-1
    • for all z\in V, D(i,z)=D(i-1,z)
    • for all (y,z)\in E:
      • 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 y\in V:
    • for all z\in V:
      • if (y,z)\in E,
        • then D(0,y,z)=w(y,z)
        • else D(0,y,z)=\infty
  • For i=1\rightarrow n
    • for all y\in V
      • for all z\in V
        • 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.