6.006- Introduction to Algorithms Lecture 14 Prof. Patrick JailletLecture overview Shortest paths – Definition – Generic algorithm – Some properties Readings: CLRS 24 (intro)Paths in graphs Consider a directed graph G = (V, E) with edge-weight function w : E → R. The weight of path p = v1 →v2 → → vk is defined to be the sum of all weights on the path, i.e., w(p) = w(v1,v2) +…+ w(vk-1,vk) v1 v2 v3 v4 v5 4 –2 –5 1 Example: w(p) = –2Shortest paths - definition • A shortest path from u to v is a path of minimum weight from u to v • The shortest-path weight δ(u, v) from u to v is defined as the weight of any shortest path from u to v Special cases: 1. no path from u to v exists: δ(u, v) = ∞# “you cannot get there from here” 2. negative weight cycles…=> undefinedWell-definedness of shortest paths If a graph G contains a negative-weight cycle, then some shortest paths may not exist. Negative weight cycles: δ(s, c) undefined (algorithm should detect such situations) ABSCDE2-21342-6Single source shortest path problem Problem: Given a directed graph G = (V, E) with edge-weight function w, and a node s, find δ(s, v) (and a corresponding path) for all v in V Today: • Generic algorithm and some structural properties Next three lectures: • Bellman-Ford: deals with negative weights • Dijkstra algorithm: fast and faster, but assumes non-negative weightsDigression Question: why can’t we just enumerate all paths to find the shortest one ? Answer: there can be exponentially many of them! s … vn 2n different paths from s to vn , 3n+1 vertices v2 v1Useful data structures • d[v] = length of best path from s to v so far • initialization d[s] = 0; d[v] = ∞ otherwise • at any step update d[v] so that d[v] ≥ δ(s, v) • π[v] = predecessor of v on a best path so far • initialization π[s] = s; π[v] = nil otherwiseA generic algorithm d[s] ← 0 π[s] ← s for each v ∈ V – {s} do d[v] ← ∞# π[v] ← nil #initialization while there is an edge (u, v) ∈ E s. t. d[v] > d[u] + w(u, v) do select one such edge “somehow” set d[v] ← d[u] + w(u, v) π[v] ← u endwhile relaxation step (the trick is in the “somehow” step…)Will not stop when negative cycles 0v134-1ud[u]1211-40-1-2210etcWhat if no negative cycle .... v1 v2 v3 v4 v5 v7 v6 4 4 4 2 2 2 1 1 1 1/2 1/2 4 8 10 12 13 14 13 10 11 12 11 4 6 8 9 10 9 6 7 8 7Analysis for previous example ... T(n)= 2+T(n-2)+1+T(n-2) = 2 T(n-2) +3 T(n)=Θ(2n/2) Let: • n+1 be the number of vertices • T(n) number of relaxations on v1,…vn+1 We have: Relax (v1,v2) and (v2,v3) Relax (v1,v3) Recursion on v3,…vn+1 Conclusion: need to be careful how we relaxAnother digression .... T(n) = C1 + C2T(n - C3)T(n) = C1 + C2T(n / C3)Exponential BadPolynomial Goodif C2 > 1, trouble! Divide & Explode C2 > 1 okay provided C3 > 1 if C3 > 1Divide & ConquerOptimal substructure Theorem. A subpath of a shortest path is a shortest path. Proof. By contradiction ... p = v0vivjvkp0jpijpjkpij’Triangle inequality Theorem. For all u, v, x ∈ V, we have δ(u, v) ≤ δ(u, x) + δ(x, v). u Proof. x v δ(u, v) δ(u, x) δ(x,
View Full Document
Unlocking...