Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm


  • 07-May-2022

Dijkstra's shortest path algorithm was invented by the late great Edger 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 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 distance to a from an is zero, that seems rather obvious, but you'll see that becomes important a bit later, the distances to all other vertices from an 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 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 an 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 an 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 an 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 calculates 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 the others. But what if we simply wanted to find the 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 closer to something that we can implement.

Your comment

+