6.006- Introduction to Algorithms Lecture 17 Prof. Patrick JailletLecture overview Shortest paths IV – review and analysis of Djikstra – speeding it up • faster special cases/implementation • one source-one target – bidirectional – goal-directed searches a b d c g f e h i j 3 8 5 5 2 7 5 8 4 5 6 6 1 4 1 6 2 (0,*)+ (3,a)+ (9,d)+ (15,e)+ (13,g)+ 9th iteration (17,h)+ (5,a)+ (7,d)+ (10,b)+ (14,i)+Dijkstra’s algorithm d[s] ← 0 for each v ∈ V – {s} do d[v] ← ∞$S ← ∅ Q ← V while Q ≠ ∅ do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) relaxation steps (Implicit DECREASE-KEY) initializationCorrectness — main argument Theorem. Dijkstra’s algorithm terminates with d[v] = δ(s, v) for all v ∈ V. Proof. It suffices to show that d[v] = δ(s, v) for every v ∈ V when v is added to S. • Suppose u is the first vertex added to S for which d[u] ≠ δ(s, u) . Let y be the first vertex in V – S along a shortest path from s to u, and let x be its predecessor: s x y u S, just before adding u.Analysis of Dijkstra degree(u) times n times DECREASE-KEY Time = Θ(n)·TEXTRACT-MIN + Θ(m)·TDECREASE-KEY while Q ≠ ∅ do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v)Analysis of Dijkstra (continued) Time = Θ(n)·TEXTRACT-MIN + Θ(m)·TDECREASE-KEY Q TEXTRACT-MIN TDECREASE-KEY Total array O(n) O(1) O(n2) binary heap O(lg n) O(lg n) O(m lg n) Fibonacci heap O(lg n) amortized O(1) amortized O(n lg n+m) worst case not covered in 6.006Special cases of edge weights • if edge weights are integral and bounded by a small constant C • use an array of lists (nC+1 “buckets”) for implementing the priority queue Q • TEXTRACT-MIN and TDECREASE-KEY take O(1) • Time_Total is then O(n+m)Single-source s, Single-target t, S.P.P. d[s] ← 0 for each v ∈ V – {s} do d[v] ← ∞$S ← ∅ Q ← V while Q ≠ ∅ do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) relaxation steps initialization stop whenever u = t !!Bi-directional Search Stforward searchbackward searchBi-directional Djikstra • Alternate forward search from s, backward search from t (follow edges backward) • df(u) distances for forward search; db(u) distances for backward search • Algorithm terminates when some vertex w has been processed, i.e., deleted from the queue of both searches, Qf and Qb s3uu’t3355wBi-directional Dijkstra, example 3u3355df (s) = 0df (u) = 3df (w) = 5Forward33355db(t) = 0db(u’) = 3db (w) = 5Backward33355df (s) = 0df (u’) = 6df (t) = 10Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5df (s) = 0db (s) = 10df (w) = 5df (u) = 3db(u’) = 3df (u’) = 6df (t) = 10uuuu’u’u’u’sssswwwwtttt33355df (s) = 0df (u’) = 6Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5db(u’) = 3uuu’u’sswwttdeleted from both queues so terminate!Bi-directional Dijkstra, example 3u3355df (s) = 0df (u) = 3df (w) = 5Forward33355db(t) = 0db(u’) = 3db (w) = 5Backward33355df (s) = 0df (u’) = 6df (t) = 10Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5df (s) = 0db (s) = 10df (w) = 5df (u) = 3db(u’) = 3df (u’) = 6df (t) = 10uuuu’u’u’u’sssswwwwtttt33355df (s) = 0df (u’) = 6Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5db(u’) = 3uuu’u’sswwttdeleted from both queues so terminate!Bi-directional Dijkstra, example 3u3355df (s) = 0df (u) = 3df (w) = 5Forward33355db(t) = 0db(u’) = 3db (w) = 5Backward33355df (s) = 0df (u’) = 6df (t) = 10Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5df (s) = 0db (s) = 10df (w) = 5df (u) = 3db(u’) = 3df (u’) = 6df (t) = 10uuuu’u’u’u’sssswwwwtttt33355df (s) = 0df (u’) = 6Forward33355db(t) = 0db(u) = 6db (w) = 5Backwarddf (u) = 3df (w) = 5db(u’) = 3uuu’u’sswwttdeleted from both queues so terminate!Goal-directed search or A* Idea: use a “potential function” λt(u) over vertices to make the target vertex t “more attractive” vv’55increasego uphilldecreasego downhillImplementation: Modify edge weights as follow: w*(u,v) = w(u,v) − λt(u) + λt(v)Goal directed search or A*, cont. Modify edge weights with potential function over vertices: w*(u,v) = w(u,v) − λt(u) + λt(v) ⇒ for any path p between s and t we have: w*(p) = w(p) − λt(s) + λt(t) ⇒ a path from s to t is a shortest path under w* iff it is a shortest path under wFeasible potential and example • Potential λt(u) is feasible if w*(u,v) = w(u,v) − λt(u) + λt(v) ≥ 0 • As a result can use Dijkstra with w* • Examples: – Euclidean plane
View Full Document
Unlocking...