This chapter provides knowledge of shortest path. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Shortest Path 3/29/14 21:11 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Shortest Paths A 8 B 8 7 5 E 2 © 2014 Goodrich, Tamassia, Goldwasser 2 C 3 0 4 2 1 9 D 8 3 5 F Shortest Paths 1 Weighted Graphs q q 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: n In a flight route graph, the weight of an edge represents the distance in miles between the endpoint airports 2555 337 HNL 43 17 LAX 1233 © 2014 Goodrich, Tamassia, Goldwasser ORD DFW Shortest Paths 849 2 14 PVD 1205 SFO 1843 802 q LGA 7 138 1120 MIA 2 1 Shortest Path 3/29/14 21:11 Shortest Paths q Given a weighted graph and two vertices u and v, we want to find a path of minimum total weight between u and v. n Length of a path is the sum of the weights of its edges. q Example: q Applications n n n Shortest path between Providence and Honolulu Internet packet routing Flight reservations Driving directions 2555 337 HNL 43 17 LAX 1233 © 2014 Goodrich, Tamassia, Goldwasser ORD DFW 849 2 14 PVD 1205 SFO 1843 802 n LGA 7 138 1120 MIA Shortest Paths 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 2555 LAX 1233 © 2014 Goodrich, Tamassia, Goldwasser 802 337 HNL 43 17 ORD DFW Shortest Paths 849 2 14 PVD 1205 SFO 1843 LGA 7 138 1120 MIA 4 2 Shortest Path 3/29/14 21:11 Dijkstra’s Algorithm q q q 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 .
