1Notes• 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 8thweek will cover Greed and Dynamic Programming, and through HW #4Topological Sorting• 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, shirt, pants, belt, …– Set of dependencies {T1àT2, T3à T4, 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 possibleTopological Sorting• TOP_SORT PROBLEM: Given a DAG G=(V,E) with |V|=n, assign labels 1,...,n to vi∈ V s.t. if v has label k, all vertices reachable from v have labels > k• “Induction idea”: – 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 doesn’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 repeatDynamic Programming Key Phrases• As we discuss shortest paths, and then the dynamic programming approach, keep in mind the following “key phrases”– “Principle of Optimality”: Any subsolution of an optimal solution is itself an optimal solution– “Overlapping Subproblems”: Can exploit a polynomiallybounded 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 instanceSingle-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 vi ∈ V, vi ≠ s.• Let L*(i,j) = length of SP from vito vj• Lemma: Suppose S ⊂ V contains s = viand L*(1,w) is known ∀ w ∈ S. For vi∉ S:– Let D(vi) = minw ∈ SL*(1,w) + L(w,i) (*)L*(1,w) = path length, with path restricted to vertices of SL(w,i) = edge length– Let vvminimize D(vi) over all nodes vi∉ S (**)Then L*(1,v) = D(vv).• 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!)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=v1, v2, …, vr= v from the source v1to v. Let vjbe the first vertex in this SP that is not in S• Then: L*(1,v) = L*(1, vj-1) + L(vj-1, vj) + L*(vj,v)// else, not a shortest path≥ D(vj) + L*(vj,v)// D(vj) minimizes over all w in S, including vj-1≥ D(v) + L*(vj,v)// because bothvjand vv∉ S, but vvchosen first≥ D(v)// since L*(vj,v) ≥ 0. Lemma à Dijkstra’s Algorithm2A Fact About Shortest Paths• Triangle Inequality:δ(u,v) ≤ δ(u,x) + δ(x,v)(shortest path distances induce a metric)uxvShortest 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• 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 transactions in arbitrage, …• Always: no negative cycles– Makes the shortest-path problem well-defined<0Shortest Paths• First case: All edges have positive length– Length of (vi,vj ) edge = dij• Condition 1: dij> 0 • Condition 2: di+ djk≤ dikfor 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 totalShortest Paths• Scenario: All shortest paths from v0= 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: Pkcontains ≤ 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 d01+ d1i– Else would have ≥ 1 paths shorter than P2, a contradictionAnother Presentation of Dijkstra’s Algorithm• Terminology– Permanent label: true SP distance from v0to vi– Temporary label: restricted SP distance from v0to vi(going through only existing permanently -labeled nodes)Permanently labeled nodes = set S in previous development• Dijkstra’s Algorithm0. All vertices vi, i = 1, …, n-1, receive temporary labels liwith value d0iLOOP:1. Among all temporary labels, pick lk = minIliand change lkto lk* (i.e., make lk‘s label permanent) // stop if no temporary labels left2. Replace all temporary labels of vk‘s neighbors, using li← min (li, lk* + dki)Prim’s