Shortest Paths A 8 B 8 2 2010 Goodrich Tamassia Shortest Paths 2 7 5 E C 3 0 2 4 1 9 D 8 F 3 5 1 Weighted Graphs In a weighted graph each edge has an associated numerical value called the weight of the edge Edge weights may represent distances costs etc Example In a flight route graph the weight of an edge represents the distance in miles between the endpoint airports 2010 Goodrich Tamassia 337 HNL 2555 3 4 17 LAX 1233 ORD DFW Shortest Paths 849 2 4 1 PVD 1205 SFO 1843 802 LGA 87 3 1 1120 10 9 9 MIA 2 Shortest Paths Given a weighted graph and two vertices u and v we want to find a path of minimum total weight between u and v Example Length of a path is the sum of the weights of its edges Shortest path between Providence and Honolulu Applications Internet packet routing Flight reservations Driving directions 2010 Goodrich Tamassia 337 HNL 2555 43 7 1 LAX 1233 ORD DFW Shortest Paths 849 2 14 PVD 1205 SFO 1843 802 LGA 87 3 1 1120 10 9 9 MIA 3 Shortest Path Properties Property 1 A subpath of a shortest path is itself a shortest path Property 2 There is a tree of shortest paths from a start vertex to all the other vertices Example Tree of shortest paths from Providence 2010 Goodrich Tamassia LAX 1233 802 337 HNL 2555 43 7 1 ORD DFW Shortest Paths 849 2 14 PVD 1205 SFO 1843 LGA 87 3 1 1120 10 9 9 MIA 4 Dijkstra s Algorithm The distance of a vertex v from a vertex s is the length of a shortest path between s and v Dijkstra s algorithm computes the distances of all the vertices from a given start vertex s Assumptions the graph is connected the edge weights are nonnegative We grow a cloud of vertices beginning with s and eventually covering all the vertices We store with each vertex v a label d v representing the distance of v from s in the subgraph consisting of the cloud and its adjacent vertices At each step 2010 Goodrich Tamassia We add to the cloud the vertex u outside the cloud with the smallest distance label d u We update the labels of the vertices adjacent to u Shortest Paths 5 Edge Relaxation Consider an edge e u z such that u is the vertex most recently added to the cloud z is not in the cloud d u 50 s The relaxation of edge e updates distance d z as follows d z min d z d u weight e 2010 Goodrich Tamassia u e d u 50 s Shortest Paths u e 10 d z 75 z 10 d z 60 z 6 Example A 8 B 2 8 7 E 2 8 1 2 7 C 3 2010 Goodrich Tamassia 0 2 4 5 B 9 F 2 7 5 E C 3 3 5 B 2 Shortest Paths 7 4 2 1 D 8 2 7 C 3 0 2 3 5 F A 5 E 0 9 8 D 11 8 2 4 1 A 8 D F A 5 E 4 9 8 B 2 3 2 C 0 4 1 9 D 8 F 5 7 3 Example cont A 8 B 2 2 7 7 C 0 2 3 5 E 4 1 9 D 8 F 3 5 A 8 B 2 2010 Goodrich Tamassia Shortest Paths 2 7 7 C 3 5 E 0 2 4 1 9 D 8 F 3 5 8 Dijkstra s Shortest Path Algorithm Find shortest path from s to t 24 2 9 s 3 18 14 6 30 11 5 5 15 4 19 6 16 20 7 6 2 44 t 9 Dijkstra s Shortest Path Algorithm S PQ s 2 3 4 5 6 7 t 0 s 24 2 9 18 14 30 11 5 5 15 4 19 6 16 20 7 6 2 6 distance label 3 44 t 10 Dijkstra s Shortest Path Algorithm S PQ s 2 3 4 5 6 7 t delmin 0 s 24 2 9 18 14 30 11 5 5 15 4 19 6 16 20 7 6 2 6 distance label 3 44 t 11 Dijkstra s Shortest Path Algorithm S s PQ 2 3 4 5 6 7 t decrease key X 9 0 s 24 2 9 18 X 14 14 30 11 5 5 15 X 15 4 19 6 16 20 7 6 2 6 distance label 3 44 t 12 Dijkstra s Shortest Path Algorithm S s PQ 2 3 4 5 6 7 t delmin X 9 0 s 24 2 9 18 X 14 14 30 11 5 5 15 X 15 4 19 6 16 20 7 6 2 6 distance label 3 44 t 13 Dijkstra s Shortest Path Algorithm S s 2 PQ 3 4 5 6 7 t X 9 0 s 24 2 9 3 18 X 14 14 6 30 11 5 5 15 X 15 4 19 6 16 20 7 6 2 44 t 14 Dijkstra s Shortest Path Algorithm S s 2 PQ 3 4 5 6 7 t decrease key X 33 X 9 0 s 24 2 9 3 18 X 14 14 6 30 11 5 5 15 X 15 4 19 6 16 20 7 6 2 44 t 15 Dijkstra s Shortest Path Algorithm S s 2 PQ 3 4 5 6 7 t X 33 X 9 0 s 24 2 9 3 delmin 18 X 14 14 6 30 11 5 5 15 X 15 4 19 6 16 20 7 6 2 44 t 16 Dijkstra s Shortest Path Algorithm S s 2 6 PQ 3 4 5 7 t 32 X X 33 X 9 0 s 24 2 9 3 18 X 14 14 6 30 44 X 11 5 5 15 X 15 4 19 6 16 20 7 6 2 44 t 17 Dijkstra s Shortest Path Algorithm S s 2 6 PQ 3 4 5 7 t 32 X X 33 X 9 0 s 24 2 9 3 18 X 14 14 6 30 44 X 11 5 5 15 4 19 6 16 20 7 X 15 6 2 44 delmin t 18 Dijkstra s Shortest Path Algorithm S s 2 6 7 PQ 3 4 5 t 32 X X 33 X 9 0 s 24 2 9 3 18 X 14 14 6 30 44 X 35 X 5 5 15 X 15 11 4 19 6 16 20 7 6 2 44 t 59 X 19 Dijkstra s Shortest Path Algorithm S s 2 6 7 PQ 3 4 5 t delmin 32 X X 33 X 9 0 s 24 2 9 3 18 X 14 14 6 30 44 X 35 X 5 5 15 X 15 11 4 19 6 16 20 7 6 2 44 t 59 X 20 Dijkstra s Shortest Path …
View Full Document
Unlocking...