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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s