Dijkstra’s Algorithm Explained

One of the classic human problems is getting from point A to point B. This is because, whenever you move, you’re faced with a choice: how are you going to get there?

If I want to get to Los Angeles from New York City, I have several options. I could use a train, a plane, or a car, and I have many different routes I could take. I could even drive to Dallas first, then fly the rest of the way. Deciding which mode of transportation and path I want to use all comes down to finding one final “total cost.” This total cost is time, hassle, and money, all combined into one easy to compare number for any one part of the trip. This is the heart of Dijkstra’s algorithm.

Dijkstra’s algorithm, given a map of points and paths between those points, will give you the cheapest path from one point to any other point. Cheapest meaning total cost, not necessarily miles or money. Going back to our NY to LA example:

Dijkstra 1

Above, you can see several different points you can go to. Notice the costs assigned to each path. Remember, this is the total cost. It is always better to take a path with a lower cost.

With this map we return to our question: what is the best way to get from NY to LA? First, let’s simplify:

Dijkstra 2

Despite the lack of city names and background map, for our purposes this simplified map is exactly the same as the first. Whatever the shortest path from A to D is will also be the shortest path for NY to LA.

On to Dijkstra’s algorithm itself, which is easy to do by hand. All we need is a chart to keep track of a few things:

Dijkstra Chart

In this chart each row represents a point on the map. The ‘cost’ column keeps track of how expensive the path that leads to that point is. The ‘previous’ column keeps track of what point is before that one in the chain back to the starting node. The default value in the cost boxes is infinity because to start with, there are no connected points, so anything would be better.

That may be a lot to take in, but I think it will become clear how it works as we go through the algorithm. The process is simple; we need to check every point’s paths against the chart. Let’s begin:

Dijkstra 3

A is the starting node, so we need to check its paths first. A to B has a cost of 3, and B’s current number in the cost column is infinity. To see if we need to update the chart, we see if the new path is less than the current cost. 3 is less than infinity, so we change that row into:

Dijkstra 4

The chart has been updated. We have the new cost of the path leading to B (3), and the previous point in the chain back to the starting point (A). Now, it’s time to do the same thing for A to C and A to D. Traveling to C from A costs 7. 7 is less than infinity. Traveling to D from A costs 9, which is also less than infinity, so we can update the chart with both of these new numbers:

Dijkstra 5

We have examined all of A’s paths, so now we can move on to point B. The first B path is B to A, however, with this algorithm, any paths leading to points that have already been examined can be skipped. B to A leads to A, and we just looked at A, so we skip that path. Next up is B to C.

To evaluate this path, I need to explain what we’re doing a bit more. You may think we should compare 1 (the cost of B to C) and 7 (the number in C’s cost column). That is almost correct. However, when we compare the numbers, we actually have to use the total cost of the current point added to the cost of the path, and the total cost of the other point.

What do I mean when I say total? Total in this case refers to the number in the point’s cost column, plus the cost of all previous points, going back to the starting point. Again, this will be more clear as we continue with the algorithm.

Back to B to C. The total cost of B (the cost all the way back to A) is 3. The cost of the path we’re looking at is 1. 3 plus 1 gives us our first number, 4. The second number is the total cost of C, which is 7. 4 is less than 7, so we update the chart again:

Dijkstra 6

Notice, we did not put 4 in the cost column, instead we have 1 there. To reiterate: the cost column is the cost of the path leading to that point, not the total cost to get to that point.

I’d like to pause for a moment to explain what else could have happened there. We updated the chart because the total cost of our new path (A to B to C) was cheaper than the cost of the old path (A directly to C).

Now imagine the path from B to C had a different cost, let’s say 20. What would we have done then? Well, the total cost comparison would have been, is 23 less than 7? 23 is, of course, not less than 7. Whenever the new number is not less than the one in the chart, you simply move on to the next path. In this example, the C column would have remained 7, A.

Back to the algorithm itself, which we can already see working. We can use the ‘previous’ column and work backwards to find the shortest path. Starting from the C row, C’s previous is B. B’s previous is A. This means the shortest path from C to A is C-B-A, which, if we look at the map, is true. There is no cheaper path from C to A.

The next path is similar to the last, B to D. adding the numbers together, We see that 6 is less than 9. So:

Dijkstra 7

Almost Done! With point C we can skip C to B and C to A, because we have already checked A and B. That leaves C to D.

To get the first number, we need C’s current total cost. At first glance, it may seem to be 1, but remember, total cost is the cost all the way back to A. So we take 1 (C-B), add that to 3 (B-A), add 2 (The new path, C-D), and we get our first number, 5.

The second number is just the total cost of D. D-B is 3 plus B-A which is also 3, which gets us 6.

5 is less than 6, so we update the chart one more time:

Dijkstra 8

We don’t actually need to check the last point, because every path it has leads to a point we’ve already done.

And with that, the Dijkstra’s algorithm is complete! The original question was: what is the best path from D to A? Looking at the chart, D’s previous is C, C’s previous is B, and B’s previous is A. What does that mean? It means the best path from A to D is A-B-C-D!

Transferring that to the other map:

Dijkstra 1

Based on the answer we got, the best way to LA from NY is NY to Bismarck to Dallas to LA. If you look carefully, you can see that there is no cheaper path between these two cities, which means Dijkstra’s algorithm has worked!

After all of that, you may not be too impressed. Just looking at the original map you could probably find the correct path pretty quickly. However, what if we had included every city and flight path in America? You might never be able to figure out the cheapest way to get anywhere! That’s the real advantage of Dijkstra’s algorithm, it works on any map of this format, no matter the size.

The other advantage is it’s relatively simple to remember. Go through each point’s paths. If the path plus the total cost of the current point is less than the total cost of the other point, update the chart. If not, move on the the next path. That, is Dijkstra’s algorithm.

 

If you want to watch my video demonstration of Dijkstra’s algorithm, you can watch that here.

You can see my implementation of Dijkstra’s algorithm on GitHub here.

To see more articles, click here.

One thought on “Dijkstra’s Algorithm Explained”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s