Shortest Paths A 8 B 2 8 2 7 5 E C 3 0 2 4 1 9 D 8 F 5 3 Outline and Reading Weighted graphs 7 1 Dijkstra s algorithm 7 1 1 Shortest path problem Shortest path properties Algorithm Edge relaxation The Bellman Ford algorithm 7 1 2 Shortest paths in dags 7 1 3 All pairs shortest paths 7 2 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 337 HNL 2555 3 4 17 LAX 1233 ORD DFW 849 2 4 1 PVD 1205 SFO 1843 802 LGA 87 3 1 1120 10 9 9 MIA Shortest Path Problem 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 337 HNL 2555 3 4 17 LAX 1233 ORD DFW 849 2 4 1 PVD 1205 SFO 1843 802 LGA 87 3 1 1120 10 9 9 MIA 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 LAX 1233 802 337 HNL 2555 43 7 1 ORD DFW 849 2 14 PVD 1205 SFO 1843 LGA 87 3 1 1120 10 9 9 MIA 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 edges are undirected 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 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 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 u e d u 50 s u e 10 d z 75 z 10 d z 60 z Example A 8 B 2 8 7 E 2 8 1 2 7 C 3 0 2 4 5 B 9 F 2 7 5 E C 3 5 3 B 2 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 3 Example cont A 8 B 2 2 7 7 C 3 5 E 0 2 4 1 9 D 8 F 3 5 A 8 B 2 2 7 7 C 3 5 E 0 2 4 1 9 D 8 F 5 3 Dijkstra s Algorithm A priority queue stores the vertices outside the cloud Locator based methods Key distance Element vertex insert k e returns a locator replaceKey l k changes the key of an item We store two labels with each vertex Distance d v label locator in priority queue Algorithm DijkstraDistances G s Q new heap based priority queue for all v G vertices if v s setDistance v 0 else setDistance v l Q insert getDistance v v setLocator v l while Q isEmpty u Q removeMin for all e G incidentEdges u relax edge e z G opposite u e r getDistance u weight e if r getDistance z setDistance z r Q replaceKey getLocator z r Analysis Graph operations Label operations Each vertex is inserted once into and removed once from the priority queue where each insertion or removal takes O log n time The key of a vertex in the priority queue is modified at most deg w times where each key change takes O log n time Dijkstra s algorithm runs in O n m log n time provided the graph is represented by the adjacency list structure We set get the distance and locator labels of vertex z O deg z times Setting getting a label takes O 1 time Priority queue operations Method incidentEdges is called once for each vertex Recall that v deg v 2m The running time can also be expressed as O m log n since the graph is connected Extension Using the template method pattern we can extend Dijkstra s algorithm to return a tree of shortest paths from the start vertex to all other vertices We store with each vertex a third label parent edge in the shortest path tree In the edge relaxation step we update the parent label Algorithm DijkstraShortestPathsTree G s for all v G vertices setParent v for all e G incidentEdges u relax edge e z G opposite u e r getDistance u weight e if r getDistance z setDistance z r setParent z e Q replaceKey getLocator z r Why Dijkstra s Algorithm Works Dijkstra s algorithm is based on the greedy method It adds vertices by increasing distance Suppose it didn t find all shortest distances Let F be the first wrong vertex the algorithm processed When the previous node D on the true shortest path was considered its distance was correct But the edge D F was relaxed at that time Thus so long as d F d D F s distance cannot be wrong That is there is no wrong vertex A 8 B 2 2 7 7 C 3 5 E 0 2 4 1 9 D 8 F 5 3 Why It Doesn t Work for Negative Weight Edges Dijkstra s algorithm is based on the greedy method It adds vertices by increasing distance 0 If a node with a negative incident edge were to be added late to the cloud it could mess up distances for vertices already in the cloud A 8 B 2 6 7 7 C 0 5 E 4 5 1 8 D 9 F 5 C s true distance is 1 but it is already in the cloud with d C 5 4 Bellman Ford Algorithm Works even with negativeweight edges Must assume directed edges for otherwise we would have negativeweight cycles Iteration i finds all shortest paths that use i edges Running time O nm Can be extended to detect a negative weight cycle if it …