Shortest Paths Shortest Paths Part 1 Shortest Path Problem Dijkstra s Shortest Path Algorithm Analysis Definitions A path in a directed graph is a sequence of vertices p v0 v1 vk s t there is an edge connecting vi to vi 1 for all i A path in an undirected graph is a sequence of vertices p v0 v1 vk s t there is an edge connecting vi and vi 1 for all i Definitions The weight of a path p v0 v1 vk is pw vw i 1 v i k i 1 The shortest path weight from vertex u to vertex v is vu min upw p v vup otherwise Applications Navigation System Suppose you want to find the distance or travel time from one POI point of interest to another POI you can ask Google https www google com maps If you need to know how to go to an address you can use an app on your phone Why doesn t your phone ask for the source Vertex attributes Initialization the current distance from the source and the current For each node we have two attributes representing predecessor of vertex will not increase in the process We initialize distance from the source to Initialize Single Source G s 1 2 3 4 for each vertex v V G do s d 0 v d v p nil Relax u v w We adjust if it reduces the distance at vertex whenever we traverse an edge Relax u v w 1 2 3 if v d u d w u v then v d u d w u v v p u Relax u v w Illustration Before 2 u 5 v 9 Relax u v w Illustration Relax u 5 92 v Relax u v w Illustration Result 2 u 5 v 7 Relax u v w Illustration Before 5 u 5 v 9 Relax u v w Illustration Relax 5 u 5 v 9 Relax u v w Illustration Result 5 u 5 v 9 Shortest Paths Part 2 Shortest Path Problem Dijkstra s Shortest Path Algorithm Analysis Dijkstra s Algorithm The idea of the algorithm is the following Use a greedy algorithm Use a priority queue Q where the key of vertex is the currently computed distance from the Processed vertices are removed from Q and stored in a set S source S Q Dijkstra s Algorithm Initialize Single Source G s for each vertex Dijkstra G w s 1 2 S 3 Q 4 Insert Q u 5 6 while Q do 7 8 9 10 11 12 u Extract Min Q S S u for each vertex v u adj do Relax u v w if the call of Relax decreases Decrease Key Q v v d Running Example s 10 5 2 3 4 6 t y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 10 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 10 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 10 5 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 10 5 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 10 5 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 10 5 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 14 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 13 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 13 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 13 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 13 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Running Example s 0 10 5 2 3 4 6 t 8 5 y 1 9 7 2 x 9 7 z Shortest Paths Part 3 Shortest Path Problem Dijkstra s Shortest Path Algorithm Analysis Running Time of Dijkstra s Algorithm The running time depends on how we implement Q If we use a binary heap to implement the priority Q Insertion takes O log V Extract Min …
View Full Document
Unlocking...