2009-12-25

Dijkstra's Shortest Path

There was an infamous professor at my university with a multiple choice exam question:

What is the correct spelling of Edsger

(A) Dykstra
(B) Dikstra
(C) Dijkstra
(D) Dyjkstra

I never did forget how to spell it—it's the fact that I-J-K appears in order that helps you to remember.

Anyway, one of Dijkstra's most famous algorithms is one to find the shortest path through a graph. The graph is a set of vertices connected by weighted edges.  Or, more concretely, a set of cities connected by roads of varying lengths. The question is, what's the shortest path from Copenhagen to Stuttgart?

Lots of times computer scientists will think long and hard about programming problems and come up with inhuman non-obvious algorithms that are actually quite effective. Often this involves a re-imagining of the problem into terms that are better suited for a computer.

In this case, the problem is restated in two interrelated sub-problems:

• For each city in the graph, calculate that city's distance from the starting point (it's distance from Copenhagen, for example).

• For each city in the graph, record which neighboring city you should go to in order to get ultimately closer to the starting point, storing the result as a "parent" pointer. (The parent pointer says "this is the shortest way back to the starting city".

Once you have the parent pointers figured out for each node, getting from a destination city back to the starting city is merely a matter of following the parent pointers all the way.

The other part of the problem, calculating the distances, is used as a stepping stone to get the parent pointers. First you initialize things like this:

1. Mark the distance from the start to itself as zero. That is, this distance from Copenhagen to Copenhagen is zero.

2. Mark the distances from all other nodes to Copenhagen as infinite.

3. Create a set that contains all the cities that we have not yet visited, namely: all the cities.

After that, we're going to visit each city in the set and figure out how far it is from Copenhagen. This is done through addition like so: if Frankfurt is 545 km from Berlin, and Berlin is 435 km from Copenhagen, then therefore Frankfurt must be 545+435 (980) km from Copenhagen, and not infinity km after all. And we then mark Frankfurt's parent as Berlin.

And here's a tricky bit: if later on we find through visiting more of the graph that there's a shortcut and Frankfurt is only 350 km from Hannover, and Hannover is 475 km to Copenhagen, we can decrease Frankfurt's distance to 350+475 (825) km from Copenhagen. And we change Frankfurt's parent over to Hannover, because now that's the shortest way back to Copenhagen.

This process of continually decreasing the distance from infinity down to its actual value is called "relaxing". Each time we relax a node, we also modify its parent pointer to point in the direction of the newly-discovered shorter route.

To perform this calculation on a search from Copenhagen to Stuttgart, we just need a few steps:

1. From the set (of all the cities—we created it, above), choose the city with the smallest distance to the source (smallest distance to Copenhagen). Let's call it C.

2. Look at C's neighbors and the length of the roads connecting them to C. Relax any neighbors that need relaxing. (That is, if city C is 100 km from Copenhagen, and it's a 50 km road to the next city, that city should have a distance of at most 100+50 (150) km from Copenhagen. If it's more, you need to relax it down to 150 and set its parent pointer to C.)

3. Remove city C from the set.

4. Repeat from step 1 until done. You're done if all the cities in the set have infinite distance (meaning they aren't connected to Copenhagen by any routes). You're also done if the set is empty (you didn't find Stuttgart on the map). And you're also done if you find your destination city of Stuttgart.

Do notice this: the city we remove from the set is always the city that's closest to the source city. If there were any closer cities, we'd have removed them first. Even though we haven't explored the far reaches of the map yet, we know the far reaches must be farther than the near reaches, because we must pass through the near reaches to reach them! We are always exploring the map by continually examining the city that we know to be closest to the source city.

As an aside at this point, you might notice that if a distance between two cities could be negative, it would mess the whole thing up. There might be a Secret One-Way Magic Portal from the "farthest" city on the map to the destination city with a distance of, say, -3490 km, making it the actual best way--but we might not find out until we'd already stopped processing at our destination. Dijkstra's Shortest Path doesn't work on graphs with negative edge weights.

A consequence of all this is that when we remove the destination city of Stuttgart from the set, we know that there are no other cities in the set that are closer to Copenhagen (because if we're removing Stuttgart from the set, it must be the closest city in the set). And so we can stop at that point.

So let's say we ran the above code and it found Stuttgart. To display the route, we start at Stuttgart and follow parent pointers all the way back to the starting city of Copenhagen, recording each city in a list as we go. This will give us a list of cities to get from Stuttgart to Copenhagen. We reverse the list so that it's from Copenhagen to Stuttgart, and show it to the user! Voila!

Bonus info: notice that the route to Copenhagen involves a ferry ride from the continent. Maybe you really hate ferry rides, so you could artificially add more "distance" to those routes making them less likely to be the shortest path. This kind of weighting can be used in all kinds of routing; if you know, for example, someone will be on a bicycle, you could decrease the weights of roads that are bicycle-friendly, and greatly increase the weights of roads that prohibit bicycles. Or you could increase the weight of very steep roads so they aren't chosen for bicycle travel.

Here's some sample code written in Python that demonstrates this. But be aware that this is not the fastest implementation and is for demonstration purposes only. Maybe later I'll show a way to speed it up.

Historic Comments

Comments