Pathfinding: Dijkstra’s Algorithm
I like tower defense games and was thinking about trying my hand at making one. But while I was making a mental checklist of things I’d need for it, it occurred to me that I would need to study pathfinding algorithms. I didn’t know the best place to start, so I went with a Google search and found the A* algorithm. Neat algorithm, but I did find plenty of notes saying that it was sort of a descendant of Dijkstra’s algorithm, and I found that was a better starting point.
You might want to know a bit about data structures, nodes, and graphs before going into this, but even if you do not, I’ll do my best to bring in as many visuals as I can and keep each step as clear as possible. I’ll also list all the references I found, and credit them as much as I can, because I am totally going to be stealing their examples.
Set-up
I’ve looked at lot of of graphs today, but I think this is the best and simplest for demonstrating Dijkstra’s algorithm. Just five nodes, or vertices because this is a graph, each with two to four edges.
Right now, I could ask you what the quickest way from A to C would be is, and you might see that the best path is A to B to C. But graphs are commonly abstractions of some relationship, and in the case of pathfinding, the vertices are specific locations and the edges are the distances between them. So what if we represented longer distances between vertices with longer edges, something like this:
However, having a graph that is more visually accurate of what it’s representing is not particularly useful in computing anything. Unsurprisingly, the best way to make this graph more algorithmically friendly is to add numbers to it, in the form of weights for the edges.
This will be the graph, vertices, and weights I’ll be using for the rest of this article. The goal will be using Dijkstra’s algorithm to find the shortest path between vertices A and C. To do this, I’ll need just a few extra things; some for helping the algorithm, and some to act as visual aides. On the algorithm side, I need two sets to hold the vertices, one called “visited” and one called “unvisited”. The algorithm is going to work through the unvisited vertex set, one at a time, and when it’s done with each vertex, it will place them in the visited set. On the visual aide side, I’ll want a table of all the vertices, to keep track of their shortest distance from vertex A, and the first vertex that was in-between them and vertex A. The final set-up will look something like this:
Stepping Through the Algorithm
The first step of the algorithm is to go through the unvisited vertices and look for the one with the shortest distance from A. At the start, everything is unvisited, and the only vertex with a known distance is A, so we start by examining A.
Now that we have a current vertex, we need to look at its unvisited neighbors, which in this case are vertices B and D. For each unvisited neighbor, we need to find their distance from vertex A. This will be more complicated later, but because we are currently measuring directly from A to these vertices, it will just be the weights on those edges: A to B is 6, and A to D is 1. With these two values in hand, we need to compare them to the current recorded shortest distance from vertex A, and if the new distance is smaller, replace that value. On the table, we can see that both B and D are still set to infinity, so 6 and 1 are definitely smaller and will be made the new shortest distance. Alongside updating the distance, we also need to record that this new shortest distance was made by a connection through the current vertex. Again, this feels silly on the first loop when it’s a clear, direct connection to A, but this is what makes the algorithm work. Finally, we can move A to the visited set, and that is one loop of the algorithm.
Rinse and Repeat
And now we start all over, going through the same steps and following the same rules. So, look at the unvisited set and find the one with the shortest distance from A. More choices this time around, but D, with a distance of 1, is clearly the shortest, so it will be the new current vertex.
Just like before, we now need to look at D’s unvisited neighbors, which are B and E. A is also a neighbor, but because it has been visited already and is in the visited set, it will not be examined, affected, or changed here. Next, we need the distance from the neighbors to A. Using E as an example, the distance from D to E on the graph is 1, and D’s shortest distance from A on the table is 1, so 1+1=2. Before, in the first loop with B and D, this would’ve looked like 0+6 and 0+1, because A was the current vertex and its shortest distance was 0. However, writing out 0+1 in that first pass just looks odd to me, so I passed over explaining it like this until now as I think it makes a little more sense on every iteration after the first.
We’ll also do this for B. D to B is 2, the D’s shortest distance is 1, so 1+2=3. Now, compare these values against the table’s values. E is still set to infinity so it obviously gets updated, but more interestingly, B is also getting updated! B’s previous shortest distance was 6, but the algorithm has now found a shorter distance of 3, so B’s record gets updated. So, even though there is a direct path from A to B, the shortest path from A to B is A > D > B. The algorithm is already working! Finally, we’ll add the current vertex to the previous vertex column for any vertices that had their shortest distances updated, and move D to the visited set.
And repeat! In the unvisited set, E currently has the shortest distance from A, with a value of 2, so it becomes the new current vertex.
E’s unvisited neighbors are B and C. Starting with C, the distance between E and C is 5, and E’s shortest distance to A is 2, 2+5=7, and 7 is shorter than infinity.
However, we get another new example with B: the distance from E to B is 2, E’s shortest distance to A is 2, 2+2=4, but oh no! There is already a shorter distance on the table, so the shortest distance to A and previous vertex for B will not be updated. So, we’ll just update C’s records, and move E to the visited set.
At this point, we have the final shortest distance from A to C, but the algorithm doesn’t know that for a fact, and still has two more vertices to process, so we’ll continue. In the unvisited set, B has the shortest distance and gets to be the new current vertex.
B’s only unvisited neighbor is C, it is distance of 5 away, add that to B’s shortest distance from 3 from A, 3+5=8. It’s close, but C currently has a shorter distance of 7 right now, so no updates this time. B is then placed in the visited set.
No skipping ahead! Let the algorithm finish its work! In the unvisited set, C has the shortest distance, which, ya know, isn’t surprising because it’s the only thing left in that unvisited set. Let’s make it the current vertex.
C does not have any unvisited neighbors, so we’ll just move it right into visited. Easy! And the algorithm is complete!
Using the Results
Our stated goal was to find the shortest path between A and C, and with this table’s information we can clearly find it. What we’ll do is trace our route backwards by using the previous vertex column.
- First, start at C, our chosen destination, and look at its previous vertex. It lists E, so we’ll then go to E’s record and previous vertex.
- It lists D, so we’ll then go to D’s record and previous vertex.
- It lists A, so that is our shortest path: A > D > E > C.
This is a small graph, so you should be able to visually confirm this, but on a larger graph where that would not be possible, this is the algorithm and process that would be taken. A real world example would your GPS providing a route to some destination: the vertices will be locations and intersections, the edges are roads, and the weights are distance between those locations. There will certainly be more to it than this, but at its very core, your GPS is using something very similar to Dijkstra’s algorithm.
References:
This is the best explanation of Dijkstra’s algorithm I found. He goes very slow, has a very good example, and has lots of visuals for each step. Frankly, I’ve cheated you. I should’ve started this article by directing you to this video and called it a day. But no, I made you read through this whole thing to get to this point.
I started off my search by finding Computerphile’s A* algorithm video, but then worked backwards to this one. Definitely a good explanation, but it’s less focused, less organized, more free form, and conversational.
Great visualization of what these pathfinding algorithms are doing, and just fun to play with.