Dijkstra algorithm ppt example

dijkstra's algorithm example step by step ppt and dijkstra's algorithm link state routing ppt
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
4. GREEDY ALGORITHMS II Dijkstra's algorithm ‣ minimum spanning trees ‣ Prim, Kruskal, Boruvka ‣ single-link clustering ‣ min-cost arborescences ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Sep 8, 2013 6:30 AM4. GREEDY ALGORITHMS II Dijkstra's algorithm ‣ minimum spanning trees ‣ Prim, Kruskal, Boruvka ‣ single-link clustering ‣ min-cost arborescences ‣ SECTION 4.4Shortest-paths problem Problem. Given a digraph G = (V, E), edge lengths ≥ 0, source s ∈ V, e and destination t ∈ V, find the shortest directed path from s to t. 3 1 15 5 4 12 source s 3 0 8 9 7 2 7 9 6 1 11 5 5 4 13 6 4 20 destination t length of path = 9 + 4 + 1 + 11 = 25 3Car navigation 4Shortest path applications PERT/CPM. Map routing. Seam carving. Robot navigation. Texture mapping. Typesetting in LaTeX. Urban traffic planning. Telemarketer operator scheduling. Routing of telecommunications messages. Network routing protocols (OSPF, BGP, RIP). Optimal truck routing through given traffic congestion pattern. Reference: Network Flows: Theory, Algorithms, and Applications, R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Prentice Hall, 1993. 5Dijkstra's algorithm Greedy approach. Maintain a set of explored nodes S for which algorithm has determined the shortest path distance d(u) from s to u. Initialize S = s , d(s) = 0. Repeatedly choose unexplored node v which minimizes shortest path to some node u in explored part, followed by a single edge (u, v) e v d(u) u S s 6Dijkstra's algorithm Greedy approach. Maintain a set of explored nodes S for which algorithm has determined the shortest path distance d(u) from s to u. Initialize S = s , d(s) = 0. Repeatedly choose unexplored node v which minimizes add v to S, and set d(v) = π(v). shortest path to some node u in explored part, followed by a single edge (u, v) d(v) e v d(u) u S s 7Dijkstra's algorithm: proof of correctness Invariant. For each node u ∈ S, d(u) is the length of the shortest s↝u path. Pf. by induction on S Base case: S = 1 is easy since S = s and d(s) = 0. Inductive hypothesis: Assume true for S = k ≥ 1. Let v be next node added to S, and let (u, v) be the final edge. The shortest s↝u path plus (u, v) is an s↝v path of length π(v). Consider any s↝v path P. We show that it is no shorter than π(v). Let (x, y) be the first edge in P that leaves S, and let P' be the subpath to x. P' y x P is already too long as soon as it reaches y. P s S u v ≥ d(x) + (x, y) ≥ π (y) ≥ π (v) (P) ≥ (P') + (x, y) ▪ definition nonnegative Dijkstra chose v inductive lengths instead of y hypothesis of π(y) 8Dijkstra's algorithm: efficient implementation Critical optimization 1. For each unexplored node v, explicitly maintain π(v) instead of computing directly from formula: π(v) = min d(u) +  . e e = (u,v) : u∈ S For each v ∉ S, π (v) can only decrease (because S only increases). More specifically, suppose u is added to S and there is an edge (u, v) € leaving u. Then, it suffices to update: π (v) = min π (v), d(u) + (u, v) Critical optimization 2. Use a priority queue to choose the unexplored node that minimizes π (v). 9Dijkstra's algorithm: efficient implementation Implementation. Algorithm stores d(v) for each explored node v. Priority queue stores π (v) for each unexplored node v. Recall: d(u) = π (u) when u is deleted from priority queue. DIJKSTRA (V, E, s) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ Create an empty priority queue. FOR EACH v ≠ s : d(v) ← ∞; d(s) ← 0. FOR EACH v ∈ V : insert v with key d(v) into priority queue. WHILE (the priority queue is not empty) u ← delete-min from priority queue. FOR EACH edge (u, v) ∈ E leaving u: IF d(v) d(u) + (u, v) decrease-key of v to d(u) + (u, v) in priority queue. d(v) ← d(u) + (u, v). _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 10Dijkstra's algorithm: which priority queue? Performance. Depends on PQ: n insert, n delete-min, m decrease-key. Array implementation optimal for dense graphs. Binary heap much faster for sparse graphs. 4-way heap worth the trouble in performance-critical situations. Fibonacci/Brodal best in theory, but not worth implementing. PQ implementation insert delete-min decrease-key total 2 unordered array O(1) O(n) O(1) O(n ) binary heap O(log n) O(log n) O(log n) O(m log n) d-way heap O(d log n) O(d log n) O(log n) O(m log n) d d d m/n (Johnson 1975) Fibonacci heap † † O(1) O(log n) O(1) O(m + n log n) (Fredman-Tarjan 1984) Brodal queue O(1) O(log n) O(1) O(m + n log n) (Brodal 1996) † amortized 11Extensions of Dijkstra's algorithm Dijkstra's algorithm and proof extend to several related problems: Shortest paths in undirected graphs: d(v) ≤ d(u) + (u, v). Maximum capacity paths: d(v) ≥ min π (u), c(u, v) . Maximum reliability paths: d(v) ≥ d(u) 𐄂 γ(u, v) . … Key algebraic structure. Closed semiring (tropical, bottleneck, Viterbi). e v d(u) u S s 124. GREEDY ALGORITHMS II Dijkstra's algorithm ‣ minimum spanning trees ‣ Prim, Kruskal, Boruvka ‣ single-link clustering ‣ min-cost arborescences ‣ SECTION 6.1Cycles and cuts Def. A path is a sequence of edges which connects a sequence of nodes. Def. A cycle is a path with no repeated nodes or edges other than the starting and ending nodes. 2 3 4 1 6 5 7 8 cycle C = (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1) 14Cycles and cuts Def. A cut is a partition of the nodes into two nonempty subsets S and V – S. Def. The cutset of a cut S is the set of edges with exactly one endpoint in S. 2 3 4 1 6 5 cut S 7 8 cutset D = (3, 4), (3, 5), (5, 6), (5, 7), (8, 7) 15Cycle-cut intersection Proposition. A cycle and a cutset intersect in an even number of edges. 2 3 4 1 6 5 7 8 cutset D = (3, 4), (3, 5), (5, 6), (5, 7), (8, 7) cycle C = (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1) intersection C ∩ D = (3, 4), (5, 6) 16Cycle-cut intersection Proposition. A cycle and a cutset intersect in an even number of edges. Pf. by picture S cycle C 17Spanning tree properties Proposition. Let T = (V, F) be a subgraph of G = (V, E). TFAE: T is a spanning tree of G. T is acyclic and connected. T is connected and has n – 1 edges. T is acyclic and has n – 1 edges. T is minimally connected: removal of any edge disconnects it. T is maximally acyclic: addition of any edge creates a cycle. T has a unique simple path between every pair of nodes. T = (V, F) 18Minimum spanning tree Given a connected graph G = (V, E) with edge costs c , an MST is a subset of e the edges T ⊆ E such that T is a spanning tree whose sum of edge costs is minimized. 24 4 23 9 6 18 16 5 11 8 7 10 14 21 MST cost = 50 = 4 + 6 + 8 + 5 + 11 + 9 + 7 n–2 can't solve by brute force Cayley's theorem. There are n spanning trees of K . n 19Applications MST is fundamental problem with diverse applications. Dithering. Cluster analysis. Max bottleneck paths. Real-time face verification. LDPC codes for error correction. Image registration with Renyi entropy. Find road networks in satellite and aerial imagery. Reducing data storage in sequencing amino acids in a protein. Model locality of particle interactions in turbulent fluid flows. Autoconfig protocol for Ethernet bridging to avoid cycles in a network. Approximation algorithms for NP-hard problems (e.g., TSP, Steiner tree). Network design (communication, electrical, hydraulic, computer, road). 20