Question? Leave a message!




Dijkstra’s algorithm

Dijkstra’s algorithm
ECE 250 Algorithms and Data Structures Dijkstra’s algorithm Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Allpairs Shortest Path 2 Outline This topic will: – Describe Dijkstra’s algorithm for finding a shortest path from a single source vertex – s3 Dijkstra’s algorithm Dijkstra’s algorithm solves the singlesource shortest path problem – It is very similar to Prim’s algorithm – Assumption: all the weights are positiveAllpairs Shortest Path 4 Strategy Suppose you are at vertex A – You are aware of all vertices adjacent to it – This information is either in an adjacency list or adjacency matrixAllpairs Shortest Path 5 Strategy Is 5 the shortest distance to B via the edge (A, B) – Why or why notAllpairs Shortest Path 6 Strategy Are you guaranteed that the shortest path to C is (A, C), or that (A, D) is the shortest path to vertex DAllpairs Shortest Path 7 Strategy We accept that (A, B) is the shortest path to vertex B from A – Let’s see where we can go from BAllpairs Shortest Path 8 Strategy By some simple arithmetic, we can determine that – There is a path (A, B, E) of length 5 + 7 = 12 – There is a path (A, B, F) of length 5 + 3 = 8Allpairs Shortest Path 9 Strategy Is (A, B, F) is the shortest path from vertex A to F – Why or why notAllpairs Shortest Path 10 Strategy Are we guaranteed that any other path we are currently aware of is also going to be the shortest pathAllpairs Shortest Path 11 Strategy Okay, let’s visit vertex F – We know the shortest path is (A, B, F) and it’s of length 8Allpairs Shortest Path 12 Strategy There are three edges exiting vertex F, so we have paths: – (A, B, F, E) of length 8 + 6 = 14 – (A, B, F, G) of length 8 + 4 = 12 – (A, B, F, C) of length 8 + 2 = 10Allpairs Shortest Path 13 Strategy By observation: – The path (A, B, F, E) is longer than (A, B, E) – The path (A, B, F, C) is shorter than the path (A, C)Allpairs Shortest Path 14 Strategy At this point, we’ve discovered the shortest paths to: – Vertex B: (A, B) of length 5 – Vertex F: (A, B, F) of length 8Allpairs Shortest Path 15 Strategy At this point, we have the shortest distances to B and F – Which remaining vertex are we currently guaranteed to have the shortest distance toAllpairs Shortest Path 16 Dijkstra’s algorithm Like Prim’s algorithm, we initially don’t know the distance to any vertex except the initial vertex – We require an array of distances, all initialized to infinity except for the source vertex, which is initialized to 0 – Each time we visit a vertex, we will examine all adjacent vertices • We need to track visited vertices—a Boolean table of size V – Do we need to track the shortest path to each vertex • That is, do I have to store (A, B, F) as the shortest path to vertex F – We really only have to record that the shortest path to vertex F came from vertex B • We would then determine that the shortest path to vertex B came from vertex A • Thus, we need an array of previous vertices, all initialized to nullAllpairs Shortest Path 17 Dijkstra’s algorithm Thus, we will iterate V times: – Find that unvisited vertex v that has a minimum distance to it – Mark it as having been visited – Consider every adjacent vertex w that is unvisited: • Is the distance to v plus the weight of the edge (v, w) less than our currently known shortest distance to w • If so, update the shortest distance to w and record v as the previous pointer – Continue iterating until all vertices are visited or all remaining vertices have a distance to them of infinity18 Example Consider the game of Risk from Parker Brothers – A game of world domination – The world is divided into 42 connected regions http://thunderbird37.com/tag/parkerbrothers/19 Example Consider the game of Risk from Parker Brothers – A game of world domination – The world is divided into 42 connected regions – The regions are vertices and edges indicate adjacent regions http://thunderbird37.com/tag/parkerbrothers/20 Example Consider the game of Risk from Parker Brothers – A game of world domination – The world is divided into 42 connected regions – The regions are vertices and edges indicate adjacent regions – The graph is sufficient to describe the game21 Example Consider the game of Risk from Parker Brothers – Here is a more abstract representation of the game board – Suddenly, it’s less interesting: ―I’ve conquered the graph‖22 Example We’ll focus on Asia http://thunderbird37.com/tag/parkerbrothers/23 Example Here is our abstract representation24 Example Let us give a weight to each of the edges25 Example Find the shortest distance from Kamchatka (K) to every other region26 Example We set up our table – Which unvisited vertex has the minimum distance to it Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø F H∞ Ø F I∞ Ø F J∞ Ø K F 0 Ø L F∞ Ø27 Example We visit vertex K Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø F H∞ Ø F I∞ Ø F J∞ Ø K T 0 Ø L F∞ Ø28 Example Vertex K has four neighbors: H, I, J and L Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø F H∞ Ø F I∞ Ø F J∞ Ø K T 0 Ø L F∞ Ø29 Example We have now found at least one path to each of these vertices Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø F H 8 K F I 12 K F J 17 K K T 0 Ø L F 16 K30 Example We’re finished with vertex K – To which vertex are we now guaranteed we have the shortest path Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø F H 8 K F I 12 K F J 17 K K T 0 Ø L F 16 K31 Example We visit vertex H: the shortest path is (K, H) of length 8 – Vertex H has four unvisited neighbors: E, G, I, L Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø T H 8 K F I 12 K F J 17 K K T 0 Ø L F 16 K32 Example Consider these paths: (K, H, E) of length 8 + 6 = 14 (K, H, G) of length 8 + 11 = 19 (K, H, I) of length 8 + 2 = 10 (K, H, L) of length 8 + 9 = 17 – Which of these are shorter than any Vertex Visited Distance Previous known path A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F∞ E Ø F∞ F Ø F∞ G Ø T H 8 K F I 12 K F J 17 K K T 0 Ø L F 16 K33 Example We already have a shorter path (K, L), but we update the other three Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø F G 19 H T H 8 K F I 10 H F J 17 K K T 0 Ø L F 16 K34 Example We are finished with vertex H – Which vertex do we visit next Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø F G 19 H T H 8 K F I 10 H F J 17 K K T 0 Ø L F 16 K35 Example The path (K, H, I) is the shortest path from K to I of length 10 – Vertex I has two unvisited neighbors: G and J Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø F G 19 H T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K36 Example Consider these paths: (K, H, I, G) of length 10 + 3 = 13 (K, H, I, J) of length 10 + 18 = 28 Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø F G 19 H T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K37 Example We have discovered a shorter path to vertex G, but (K, J) is still the shortest known path to vertex J Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø F G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K38 Example Which vertex can we visit next Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø F G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K39 Example The path (K, H, I, G) is the shortest path from K to G of length 13 – Vertex G has three unvisited neighbors: E, F and J Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K40 Example Consider these paths: (K, H, I, G, E) of length 13 + 15 = 28 (K, H, I, G, F) of length 13 + 4 = 17 (K, H, I, G, J) of length 13 + 19 = 32 – Which do we Vertex Visited Distance Previous update A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F∞ F Ø T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K41 Example We have now found a path to vertex F Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K42 Example Where do we visit next Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø F E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K43 Example The path (K, H, E) is the shortest path from K to E of length 14 – Vertex G has four unvisited neighbors: B, C, D and F Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K44 Example The path (K, H, E) is the shortest path from K to E of length 14 – Vertex G has four unvisited neighbors: B, C, D and F Vertex Visited Distance Previous A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K45 Example Consider these paths: (K, H, E, B) of length 14 + 5 = 19 (K, H, E, C) of length 14 + 1 = 15 (K, H, E, D) of length 14 + 10 = 24 (K, H, E, F) of length 14 + 22 = 36 – Which do we Vertex Visited Distance Previous update A F∞ Ø B F∞ Ø C F∞ Ø D F∞ Ø T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K46 Example We’ve discovered paths to vertices B, C, D Vertex Visited Distance Previous A F∞ Ø B F 19 E C F 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K47 Example Which vertex is next Vertex Visited Distance Previous A F∞ Ø B F 19 E C F 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K48 Example We’ve found that the path (K, H, E, C) of length 15 is the shortest path from K to C – Vertex C has one unvisited neighbor, B Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K49 Example The path (K, H, E, C, B) is of length 15 + 7 = 22 – We have already discovered a shorter path through vertex E Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K50 Example Where to next Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L F 16 K51 Example We now know that (K, L) is the shortest path between these two points – Vertex L has no unvisited neighbors Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L T 16 K52 Example Where to next – Does it matter if we visit vertex F first or vertex J first Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H F F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L T 16 K53 Example Let’s visit vertex F first – It has one unvisited neighbor, vertex D Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L T 16 K54 Example The path (K, H, I, G, F, D) is of length 17 + 14 = 31 – This is longer than the path we’ve already discovered Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H F J 17 K K T 0 Ø L T 16 K55 Example Now we visit vertex J – It has no unvisited neighbors Vertex Visited Distance Previous A F∞ Ø B F 19 E C T 15 E D F 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H T J 17 K K T 0 Ø L T 16 K56 Example Next we visit vertex B, which has two unvisited neighbors: (K, H, E, B, A) of length 19 + 20 = 39 (K, H, E, B, D) of length 19 + 13 = 32 – We update the path length to A Vertex Visited Distance Previous A F 39 B B T 19 E C T 15 E D F 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H T J 17 K K T 0 Ø L T 16 K57 Example Next we visit vertex D – The path (K, H, E, D, A) is of length 24 + 21 = 45 – We don’t update A Vertex Visited Distance Previous A F 39 B B T 19 E C T 15 E D T 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H T J 17 K K T 0 Ø L T 16 K58 Example Finally, we visit vertex A – It has no unvisited neighbors and there are no unvisited vertices left – We are done Vertex Visited Distance Previous A T 39 B B T 19 E C T 15 E D T 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H T J 17 K K T 0 Ø L T 16 K59 Example Thus, we have found the shortest path from vertex K to each of the other vertices Vertex Visited Distance Previous A T 39 B B T 19 E C T 15 E D T 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H T J 17 K K T 0 Ø L T 16 K60 Example Using the previous pointers, we can reconstruct the paths Vertex Visited Distance Previous A T 39 B B T 19 E C T 15 E D T 24 E T E 14 H T F 17 G T G 13 I T H 8 K T I 10 H T J 17 K K T 0 Ø L T 16 K61 Example Note that this table defines a rooted parental tree – The source vertex K is at the root – The previous pointer is the parent of the vertex in the tree Vertex Previous A B B E C E D E E H F G G I H K I H J K K Ø L K62 Comments on Dijkstra’s algorithm Questions: – What if at some point, all unvisited vertices have a distance ∞ • This means that the graph is unconnected • We have found the shortest paths to all vertices in the connected subgraph containing the source vertex – What if we just want to find the shortest path between vertices v and v j k • Apply the same algorithm, but stop when we are visiting vertex v k – Does the algorithm change if we have a directed graph • No63 Implementation and analysis The initialization requires Q(V) memory and run time We iterate V – 1 times, each time finding next closest vertex to the source – Iterating through the table requires is Q(V) time – Each time we find a vertex, we must check all of its neighbors 2 – With an adjacency matrix, the run time is Q(V(V + V)) = Q(V ) 2 2 2 – With an adjacency list, the run time is Q(V + E) = Q(V ) as E = O(V ) Can we do better – Recall, we only need the closest vertex – How about a priority queue • Assume we are using a binary heap • We will have to update the heap structure—this requires additional work64 Implementation and analysis The initialization still requires Q(V) memory and run time – The priority queue will also requires O(V) memory – We must use an adjacency list, not an adjacency matrix We iterate V times, each time finding the closest vertex to the source – Place the distances into a priority queue – The size of the priority queue is O(V) – Thus, the work required for this is O(V ln(V)) Is this all the work that is necessary – Recall that each edge visited may result in a new edge being pushed to the very top of the heap – Thus, the work required for this is O(E ln(V)) Thus, the total run time is O(V ln(V) + E ln(V)) = O(E ln(V))Allpairs Shortest Path 65 Implementation and analysis Here is an example of a worstcase scenario: – Immediately, all of the vertices are placed into the queue – Each time a vertex is visited, all the remaining vertices are checked, and in succession, each is pushed to the top of the binary heap66 Implementation and analysis We could use a different heap structure: – A Fibonacci heap is a nodebased heap – Pop is still O(ln(V)), but inserting and moving a key is Q(1) – Thus, because we are only calling pop V – 1 times, the work required reduces to O(E + V ln(V)) – Thus, the overall runtime is O(E + V ln(V))67 Implementation and analysis Thus, we have two run times when using – A binary heap: O(E ln(V)) – A Fibonacci heap: O(E + V ln(V)) 2 Questions: Which is faster if E = Q(V) How about if E = Q(V )68 Triangle Inequality If the distances satisfy the triangle inequality, – That is, the distance between a and b is less than the distance from a to c plus the distance from c to b, we can use the A search which is faster than Dijkstra’s algorithm – All Euclidean distances satisfy the triangle inequality http://xkcd.com/85/69 Negative Weights If some of the edges have negative weight, so long as there are no cycles with negative weight, the BellmanFord algorithm will find the minimum distance – It is slower than Dijkstra’s algorithm http://xkcd.com/69/70 Summary We have seen an algorithm for finding singlesource shortest paths – Start with the initial vertex – Continue finding the next vertex that is closest Dijkstra’s algorithm always finds the next closest vertex – It solves the problem in O(E + V ln(V)) timeAllpairs Shortest Path 71 References Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, The MIT Press, 2001, §25.2, pp.62935. Mark A. Weiss, rd Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, 2006, Ch., p.. Joh Kleinberg and Eva Tardos, Algorithm Design, Pearson, 2006. Elliot B. Koffman and Paul A.T. Wolfgang, Objects, Abstractions, Data Structures and Design using C++, Wiley, 2006. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment