Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm

Dijkstra's shortest path algorithm was invented by the late great Edsger Dijkstra a famous Dutch computer scientist the objective of the algorithm is to find the shortest path between any two vertices in a graph in fact Dijkstra's algorithm will find the shortest path from a given starting vertex to every other vertex in the graph consider this simple graph our objective is to find the shortest path from a to every other vertex once it is run Dijkstra's algorithm will generate this information which includes everything we need to know we have the shortest total distance from the starting vertex to all of the other vertices the total shortest distance from A to B is 3 from A to C it's 7 from A to D 1 and from A to E it's 2 we also have the shortest sequence of vertices from a to every other vertex in other words the shortest path for example to get from A to C notice that we arrived at C via E this is shown in the previous vertex column when we examine the information for e we can see that we arrived at E via D and when we examine the information for D we can see that we arrived at D via a so the previous vertex column actually gives us the shortest path from a to every other vertex so how does Dijkstra's algorithm go about generating this information Dijkstra's shortest path algorithm works as follows we're using two lists one to keep track of the vertices that we visited and another to keep track of the vertices that we haven't visited yet so let's consider the starting vertex a the distance to a from a is zero that seems rather obvious but you'll see that becomes important a bit later the distances to all other vertices from a are unknown so for the purposes of the algorithm we're going to set them to a very high value let's say infinity we can include this information in our table straight away now the algorithm begins good and proper we'll start by visiting the unvisited vertex with the smallest known distance from the start vertex first time around this is the start vertex itself it's a for the current vertex we then examine its unvisited neighbors well we're currently visiting a and its unvisited neighbors are B and D these are the vertices that a shares edges with for the current vertex we calculate the distance of each neighbor from the start vertex this may seem like overstating the obvious at the moment but it'll become apparent why we state it like this a little bit later for now the distance from A to B is nothing plus 6 which is 6 and from A to D is nothing plus 1 which is 1 if the calculated distance of a vertex is less than the known distance we can update the shortest distance in our table well at the moment all of our shortest distances are infinity so we can update these two distances now we update the previous vertex for each of the updated distances in this case we visited B and D via a so we'll write this information into the previous vertex column now add the current vertex to the list of visited vertices we won't be visiting a again now the algorithm begins to repeat visit the unvisited vertex with the smallest known distance from the start vertex this time around we can see in the table that its vertex D for the current vertex examine its unvisited neighbors we're currently visiting D and its unvisited neighbors are B and E for the current vertex calculate the distance of each neighbor from the start vertex the distance of B from a is the one which we've already written into the table the distance from A to D plus another two giving us a total distance of three the distance from A to E is the distance from A to D which we've already calculated and written into the table one plus another one from D to e giving us a total distance of two if the calculated distance of a vertex is less than the known distance update the shortest distance the shortest known distance from A to B as written in the table is six we've just calculated a new shortest distance of three the shortest known distance from A to E as per the table is infinity and again we've calculated a much shorter distance from A to E so we can write these values into the table replacing the previous values we found some shorter paths now we update the previous vertex for each of the updated distances in this case we visited B and D via D so we write this information into the table add the current vertex to the list of visited vertices we won't be visiting D again and once again visit the unvisited vertex with the smallest known distance from the start vertex this time around the information in the table tells us that it's vertex E for the current vertex examine its unvisited neighbors we're currently visiting E and its unvisited neighbors are b and c for the current vertex calculate the distance of each neighbor from this start vertex and again using the information in the table we can see that the total distance to B is 2 from the table the distance to e plus another 2 giving us 4 and we can see that the total distance to see from a is 2 the distance to e from the table plus another 5 giving us a total of 7 if the calculated distance of a vertex is less than the known distance update the shortest distance well we don't need to update the distance of B this time we've calculated for but our table indicates that we've already got a shorter path so we'll leave that alone on the other hand the total distance to see that we've just calculated is 7 in the table it's currently infinity so obviously we're going to overwrite that and since we've updated the value for C we're going to update the previous vertex per C in this case we visited C by re we add the current vertex to the list of visited vertices we won't be visiting a again and as before we visit the unvisited vertex with the smallest known distance from the start vertex this time around it's B for the current vertex examine its unvisited neighbors while we're currently visiting B and it's only unvisited neighbor is C for the current vertex calculate the distance of each neighbor from the start vertex so performing the same calculation again we find that our total distance from A to C is 8 if the calculated distance of a vertex is less than the known distance update the shortest distance well the value in the table for C is currently 7 so we don't need to do this update the previous vertex for each of the updated distances no distances were updated so we don't need to do this either add the current vertex to the list of visited vertices B won't be visited again visit the unvisited vertex with the smallest known distance from the starting vertex this time around it's C and for the current vertex examine its unvisited neighbors well we're currently visiting C but it doesn't have any unvisited neighbors there's nothing to do but to add the current vertex to the list of visited vertices there are no more vertices to visit so our table of information is complete let's just put those steps together into an algorithm you can see all I've done is rewrite those steps inside a repeat until loop it's worth pointing out that Dijkstra's shortest path algorithm is an example of a greedy algorithm and that's because of this step in which we're selecting the next vertex to visit the algorithm chooses the unvisited vertex with the smallest known distance from the start vertex the truth is we could select the next unvisited vertex using pretty much any criteria we like but the assumption here is that if we select the closest one to the start every time we will get to the end more quickly to define a greedy algorithm more succinctly we say that it makes locally optimal choices at each stage in the hope of finding the global optimum with some graphs this greedy approach is desirable particularly if we want to find the shortest paths from a starting vertex to all of the others but what if we simply wanted to find a shortest path from A to E in this graph the short-sighted greedy approach would result in unnecessary processing here I've just refined it slightly but it's essentially the same information a little bit closer to something that we can implement

Channel: Computer Science

Views: 812,245

Rating: 4.9402046 out of 5

Keywords: graph, dynamic data structure, vertex, edge, shortest path, Dijkstra, algorithm, greedy algorithm, path, A Level, Computer Science, Decision Mathematics

Id: pVfj6mxhdMw

Length: 10min 52sec (652 seconds)

Published: Sat May 07 2016