Written by Elliot
on May 13, 2008 |
Tonight I’d like to write a bit about Dijkstra’s algorithm. If it’s possible to make Dijkstra’s algorithm easy, I hope to do it.
The name “Dijkstra” sounds technical. But in reality the algorithm is largely common sense. Dijkstra’s algorithm is simply a way of finding the shortest path between two nodes in a graph.
To begin thinking about it, we need some foundations. The first thing is what we call a “graph.” Graphs are a bunch of dots (nodes or vertices) connected by lines (edges). The edges have a length (or “weight”). We can make up a “path” through the graph connecting two nodes of our choosing. For complex graphs, there could be many possible ways of getting from point A to point B. We can use Dijkstra’s algorithm, a series of steps, to find the shortest way.
If there are multiple shortest ways, Dijkstra should give us one of them. In that way, it’s “nondeterministic:” we don’t really know which one of the ways it will give us.
The first step is to take the starting point (or node) and “expand” it. That means we list all the nodes that are connected to it by an edge. We label these edges with their weights, and label the nodes themselves with the weight, too. We mark a node “visited” after it’s expanded.
Then we expand each of these nodes, labeling the edges with their weights. But this time, the weight label on the nodes themselves will be the total weight of the edges we had to cross in order to get here. If we start repeating some nodes, that’s OK. We know that if there are multiple ways of getting to a node, the shortest path must use the shortest way. So we can “prune” (stop looking at, or stop expanding) duplicate node names which have a higher weight.
By repeating these steps, we’ll eventually find a path to point B. But don’t stop there. We need to keep going until every node has been visited, because one of the other nodes might show us a shorter path to B. This is tricky, because it’s the one place where you might stop too early.
Basically, you expand everything and go along the path that is the shortest. So there’s really no magic behind it; in my opinion, once you try it out a few times, you’ll see it’s common sense.