Dijkstra's algorithm example step by step ppt

dijkstra's algorithm in data structure with example ppt and dijkstra's algorithm powerpoint presentation
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.All-pairs 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 single-source shortest path problem – It is very similar to Prim’s algorithm – Assumption: all the weights are positiveAll-pairs 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 matrixAll-pairs Shortest Path 5 Strategy Is 5 the shortest distance to B via the edge (A, B)? – Why or why not?All-pairs 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 D?All-pairs 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 BAll-pairs 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 = 8All-pairs Shortest Path 9 Strategy Is (A, B, F) is the shortest path from vertex A to F? – Why or why not?All-pairs Shortest Path 10 Strategy Are we guaranteed that any other path we are currently aware of is also going to be the shortest path?All-pairs Shortest Path 11 Strategy Okay, let’s visit vertex F – We know the shortest path is (A, B, F) and it’s of length 8All-pairs 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 = 10All-pairs 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)All-pairs 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 8All-pairs 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 to?All-pairs 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 nullAll-pairs 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/parker-brothers/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/parker-brothers/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 game