Stanford University CS161: Algorithms Luca Trevisan

Handout 8 April 24, 2013

Lecture 8
In which we introduce dynamic programming.

Shortest Paths with Negative Weights

In the shortest path problem we are given a graph G = (V, E ), a weight function (, ) assigning a weight (u, v ) to each edge (u, v ) E , and two vertices s, t, and we want to nd a path from s to t that minimizes the sum of the weights of the edges along the path. Dijkstras algorithm, described in the previous lecture, solves the problem assuming that all weights are greater than or equal to zero. What happens if some weights are negative? Then Dijkstras algorithm may return an incorrect solution. For example, if Dijkstras algorithm is applied to the graph below and s = A, the algorithm will initially correctly set dist[A] = 0, but then at the next step it will set dist[C ] = 1, and at the third step it will set dist[D] = 2, even though the correct values are 0 and 1, respectively.

The place where the proof of correctness breaks down is when we look at the vertex v S that minimizes min(u,v)E,uS dist[u] + (v ), and we reason that the path from s 1

to v via the shortest path from s to u followed by the edge (u, v ) must be the shortest path from s to v , because otherwise the rst place where another, shorter, path from s to v leaves S would contradict the denition of v . This assumes that an initial segment of a path is shorter than the overall path, which is false in graphs that have edges with negative weights. If we want to solve the shortest path problem in graphs that are allowed to have negative-weight edges, we rst have to be careful about the denition of the problem. The denition of a path from s to t is a sequence of nodes v0 , . . . , vk such that v0 = S , vk = t and (vi , vi+1 ) E for each i = 0, . . . , k 1. The denition allows vertices (and/or edges) to appear in the path several times. (A path in which no vertex is repeated is called a simple path.) When all edge weights are 0, then there is an optimal solution that is a simple path, and if the weights are strictly positive then only simple paths can be optimal solutions. (If v0 , . . . , vi , . . . , vj , . . . , vk is a path in which vi = vj , then just remove the segment vi , . . . , vj 1 from the path; this is still a path and length is smaller than or equal to what it was before. Repeat this process to transform any optimal path into an optimal simple path.) If a graph with negative edges has a negative cycle, then one can construct paths of arbitrarily small weight, by going around the cycle more and more times: in such a case, there is not optimal solution to the shortest path problem. To make the problem meaningful, we have the following options: 1. Work only with directed graphs that have no negative cycle. (In an undirected graph, the presence of a negative edge (u, v ) immediately creates the negative cycle u, v, u, so the requirement of having no negative edge can be satised only in directed graphs.) In such graphs, it is still true that there is an optimal solution that is a simple path, and so the optimum must be a nite number and the problem is well dened. 2. Work with arbitrary graphs, but look for the minimum weight simple path. Unfortunately this problem is NP-hard, and it is unlikely to have an ecient algorithm. We will go with option (1), and we will develop a dynamic programming algorithm. One way to think about dynamic programming is as an ecient implementation of divide-and-conquer algorithm that can speed up exponential time recursive algorithms to polynomial time iterative ones. If we start thinking about the shortest path problem with negative weights in terms of divide-and-conquer, we see that, unless s = t, a shortest path from s to t will be a shortest path from s to a vertex v , followed by the edge (v, t). So if we compute sp(s, v ), the length of the shortest path from s to v , for each v such that (v, t) is an edge, then sp(s, t) will be the minimum of sp(s, v ) + (v, t). If we implement this 2

observation as a recursive algorithm we would get a non-terminating procedure, but we can make the additional observation that we only need to look for paths from s to t that use at most n 1 edges, because we know that there is an optimal solution that is a simple path, and a simple path can have at most n vertices and so at most n 1 edges. Furthermore, if we are looking for a path from s to t that uses k edges, we will only need to look at paths from s to v of length at most k 1. We may dene the edge-restricted shortest path function ersp(s, t, k ) to be the length of the shortest path from s to t that uses at most k edges, and observe that the shortest path from s to t is ersp(s, t, n 1) and that ersp(, , ) obeys the following properties:

ersp(s, t, k ) = 0 ersp(s, t, k ) = ersp(s, t, k ) = min ersp(s, v, k 1) + (v, t)

if s = t if s = t and (k = 0 or indegree(t) = 0) if s = t, indegree(k ) > 0, and k 1

We can immediately convert the above equations into a recursive algorithm Algorithm 1 Recursive algorithm to nd shortest paths. function rec-sp(G, , s, t, k ) if s == t then return 0 else if k == 0 or indegree(t) == 0 then return else return minv:(v,t)E rec-sp(G, , s, v, k 1) + (u, v ) end if end function function shortestpath(G, , s, t) n number of vertices of G return rec-sp(G, , s, t, n 1) end function Unfortunately the algorithm has exponential running time: if, for example, all vertices have indegree 3, and T (n, k ) is the worst-case running time for a graph with n vertices and parameter k , we have T (n, k ) = 3 T (n, k 1) + O(1) (assuming we have a reverse adjacency list in the representation of G, so that the list of v such that (v, t) E can be found in time O(indegree(t)) given t) which solves to more than 3k . If we trace the execution of the algorithm on graphs in which it takes exponential time, we see that the algorithm keeps making the same recursive calls over and over, 3

because there are only n2 possible recursive calls to make (there are n possibilities for the vertex v and n possibilities for the parameter k ). The idea of dynamic programming is to compute all the answers to all possible recursive calls iteratively, starting from the bottom cases of the recursion and working up. We will construct a 2-dimensional array T [, ] where T [v, k ] will contain ersp(s, v, k ). If we loop over all values of k (from 0 to n 1) and all vertices k , we can ll up the array by simply using the recursive denition of ersp(). Algorithm 2 Dynamic programming algorithm to nd shortest paths. function dp-sp(G, , s) n number of vertices of G allocate n n array T for k = 0 to n 1 do for all vertices v do if s == v then T [v, k ] 0 else if k == 0 or indegree(t) == 0 then T [v, k ] else T [v, k ] minv:(v,t)E T [v, k 1] + (u, v ) end if end for end for return T [:, n 1] end function Assuming again that we have a reverse adjacency list in the representation of G, which can be precomputed in time O(|V | + |E |) time, each iteration of the inner loop can be executed in time O(indegree(v )), and so the total running time is O(|V | |E |). The algorithm, as described, uses O(|V |2 ) memory, but, at every step, we only use the two n-dimensional arrays T [:, k ] and T [:, k 1], so it is possible to implement the algorithm so that it uses only O(|V |) memory.

All-pairs Shortest Paths

Suppose that we want to nd the length of the shortest paths between all pairs of vertices in a graph that has negative edges but no negative cycle. Then we could apply the algorithm of the previous section to each start vertex s, and get a running time O(|V |2 |E |). It is possible, however, to get the better running time O(|V |3 ). As before, we want to add a parameter k to the problem so that it becomes trivial when k = 0, it is the problem that we are interested in when k is order of n, and such that the problem with parameter k is easily solvable if we already have solved the problem with parameter k 1. For the all-pairs shortest path problem, instead of 4

restricting the number of edges of the path, we will restrict which vertices are allowed to appear in the path as intermediate vertices. This will also restrict the length of the path, but it adds additional constraints, so that we have fewer degrees of freedoms to consider when reducing the problem with parameter k to the problem with parameter k 1, which will mean that we can implement the algorithm more eciently. Call the vertices v1 , . . . , vn , after ordering them in an arbitrary way, and dene the vertex-restricted shortest path function as follows: ersp(s, t, k ) is the length of the path from s to t which is shortest among all paths that are only allowed vertices from {v1 , . . . , vk } as intermediate vertices. The point of this denition is that either ersp(s, t, k ) is realized via a path that does not use vk , in which case ersp(s, t, k ) = ersp(s, t, k 1) or it is realized via a path that uses vk , but exactly once, so that the path goes from s to vk and then from vk to t using only a subset of the vertices in {v1 , . . . , vk1 } as intermediate vertices, meaning that ersp(s, t, k ) = ersp(s, vk , k 1) + ersp(vk , t, k 1) Notice that now we have only two cases to consider, instead of indegree(t) cases. Algorithm 3 Dynamic programming algorithm to nd all-pairs shortest paths. function dp-sp(G, ) n number of vertices of G allocate n n n array T for k = 0 to n 1 do for all vertices s do for all vertices t do if k == 0 then T [s, t, k ] 0 if s == t and T [s, t, k ] otherwise else if k == 1 then T [s, t, k ] (s, t) if (s, t) E and T [s, t, k ] otherwise else T [s, t, k ] min{T [s, t, k ], T [s, vk , k 1] + T [vk , t, k 1]} end if end for end for end for return T [:, :, n 1] end function The running time of the inner loop is O(1), and it is repeated O(|V |3 ) time, so the running time is O(|V |3 ). The memory use can be decreased to O(|V |2 ) by noting that, at each step, we are only using T [:, :, k ] and T [:, :, k 1]. 5

Independent Set on a Path

In a graph G = (V, E ), and independent set is a set of vertices S V such that there is no edge (u, v ) E such that both u S and v S . If vertices represent tasks and edges represents conicts, an independent set is a set of non-conicting tasks. In the weighted independent set problem, we are given a graph G = (V, E ) and a weight w(v ) for each vertex v V , and we want to nd an independent set S that maximizes the total weight vS w(v ). Even when all weights are 1, the problem is NP-hard and it is unlikely to have a polynomial time algorithm, but it is solvable in polynomial time in certain simple types of graphs. If the graph is a path, then it is easy to see that, if all weights are 1, then it is optimal to pick ever other vertex. This is not necessarily true, however, if there are weights. In the graph below, for example, it is optimal to pick the vertices B and E .

As before, we want to nd an additional parameter k such that the problem is trivial when k is small, is the problem that we are interested in when k is large, and there is an easy to way to solve the problem for k when we have solutions for k 1. If we call the vertices v1 , . . . , vn , where (vi , vi+1 ) are the edges of the path, then the natural idea is to call is(k ) the weight of the optimal independent set among subsets of the rst k vertices. If the k -th vertex is needed to get the optimum of is(k ), then we cannot use vk1 , and we have is(k ) = is(k 2) + w(vk ). If the k -th vertex is not needed, then is(k ) = is(k 1). Algorithm 4 Dynamic programming algorithm to nd the maximum independent set of a weighted path. The path is described just by the parameter n, and it contains vertices 1, . . . , n and edges (i, i + 1). function dp-is(n, w) allocate size-n array T T [0] 0 T [1] w(1) for k = 2 to n do T [k ] max{T [k 1], T [k 2] + w(k ) end for return T [n] end function The running time is O(|V |) and the memory use can be reduced to O(1). 6