Notes Topological Sorting This set of slides Handout 7 is missing the material on Reductions and Greed that was presented in class Those slides are still under construction and will be posted as Handout 6 The quiz on Thursday of 8th week will cover Greed and Dynamic Programming and through HW 4 Prelude to shortest paths Generic scheduling problem Input Set of tasks T1 T2 T3 Tn Example getting dressed in the morning put on shoes socks s hirt pants belt Set of dependencies T1 T 2 T3 T 4 T5 T1 Example must put on socks before shoes pants before belt Want ordering of tasks which is consistent with dependencies Problem representation Directed Acyclic Graph Vertices tasks Directed Edges dependencies Acyclic if cycle of dependencies no solution possible Topological Sorting Dynamic Programming Key Phrases TOP SORT PROBLEM Given a DAG G V E with V n assign labels 1 n to v i V s t if v has label k all vertices reachable from v have labels k Induction idea As we discuss shortest paths and then the dynamic programming approach keep in mind the following key phrases Know how to label DAG s with n vertices Claim A DAG G always has some vertex with indegree 0 Take an arbitrary vertex v If v doesn t have indegree 0 traverse any incoming edge to reach a predecessor of v If this vertex d oesn t have indegree 0 traverse any incoming edge to reach a predecessor etc Eventually this process will either identify a vertex with indegree 0 or else reach a vertex that has been reached previously a contradiction given that G is acyclic Inductive approach Find v with indegree v 0 give it lowest available label then delete v and incident edges update degrees of remaining vertices and repeat Single Source Shortest Paths Given G V E a directed graph L E a length function and a distinguished source s V Find the shortest path in G from s to each v i V v i s Let L i j length of SP from v i to v j Lemma Suppose S V contains s v i and L 1 w is known w S For v i S Let D v i minw S L 1 w L w i L 1 w path length with path restricted to vertices of S L w i edge length Let v v minimize D v i over all nodes v i S Then L 1 v D v v Notation D v length of the 1 to v SP that uses only vertices of S except for v D v is not necessarily the same as L 1 v because the path is restricted Principle of Optimality Any subsolution of an optimal solution is itself an optimal solution Overlapping Subproblems Can exploit a polynomially bounded number of possible subproblems Bottom Up D Q Table cache of Subproblem Solutions avoid recomputation by tabulating subproblem solutions Relaxation Successive Approximation Often the DP approach makes multiple passes each time solving a less restricted version of the original problem instance Eventually solve completely unrestricted original problem ins tance Single Source Shortest Paths Proof of Lemma To prove equality prove and L 1 v D v is obvious because D v is the minimum length of a restricted path while L 1 v is unrestricted Let L 1 v be the shortest path s v 1 v 2 v r v from the source v 1 to v Let v j be the first vertex in this SP that is not in S Then L 1 v L 1 v j 1 L v j 1 v j L v j v else not a shortest path D v j L v j v D v j minimizes over all w in S including v j 1 D v L v j v because bothv j and v v S but v v chosen first D v since L v j v 0 Lemma Dijkstra s Algorithm 1 A Fact About Shortest Paths Shortest Path Formulations Given a graph G V E and w E 1 to 2 s t Find a shortest path from s to t 1 to all single source Find a shortest path from a source s to every other vertex v V All to all all pairs Find a shortest path from every vertex to every other vertex Triangle Inequality u v u x x v shortest path distances induce a metric u v Weight of path v 1 v k w v i v i 1 Sometimes no negative edges Examples of negative edges travel inducements exothermic reactions in chemistry unprofitable 0 transactions in arbitrage x Always no negative cycles Makes the shortest path problem well defined Shortest Paths First case All edges have positive length Length of v v i j edge dij Condition 1 d ij 0 Condition 2 d i d jk dik for some i j k else shortest path problem would be trivial Observation 1 Length of a path length of any of its subpaths Observation 2 Any subpath of a shortest path is itself a shortest path Principle of Optimality Observation 3 Any shortest path contains n 1 edges pigeonhole principle assumes no negative cycles n nodes total Shortest Paths Scenario All shortest paths from v 0 source to other nodes are ordered by increasing length P1 P2 Pn 1 Index nodes accordingly Algorithm Find P1 then find P2 etc Q How many edges are there in P1 Exactly 1 edge else can find a subpath that is shorter Q How many edges are there in Pk At most k edges else can find k shorter subpaths which would contradict the definition of Pk Observation 4 Pk contains k edges To find P1 only look at one edge paths min P1 To find P2 only look at one and two edge paths But need only consider two edge paths of form d 01 d 1i Else would have 1 paths shorter than P2 a contradiction Another Presentation of Dijkstra s Algorithm Terminology Permanent label true SP distance from v 0 to v i Temporary label restricted SP distance from v 0 to v i going through only existing permanently labeled nodes Permanently labeled nodes set S in previous development Prim s Algorithm vs Dijkstra s Algorithm Dijkstra s Algorithm 0 All vertices v i i 1 n 1 receive temporary labels li with value d0i LOOP 1 Among all temporary labels pick lk minI li and change lk to lk i e make lk s label permanent stop if no temporary labels left 2 Replace all temporary labels of v k s neighbors using li min li lk dki Prim Iteratively add edge eij to T such that v i T v j T and dij is minimum Dijkstra Iteratively add edge eij to T such that v i T v j T and li dij is minimum Both are building trees in very similar ways Prim Minimum Spanning Tree Dijkstra Shortest Path Tree What kind of tree does the following algorithm build Prim Dijkstra Iteratively add edge …