Recently I started working on a library in Haskell that would implement dijkstra\u2019s algorithm both for fun and for an upcoming project. What I learned is that I didn\u2019t initially understand dijkstra\u2019s algorithm as well as I had thought and many of the explanations out there weren\u2019t very good and often relied on showing an example of it in action.<\/p>\n
\nTeach principles, not formulas.<\/p>\n
– Richard Feynman<\/p>\n<\/blockquote>\n
Let\u2019s learn the logic behind Dijkstra\u2019s algorithm, shall we?<\/p>\n
What\u2019s the point of it?<\/b><\/h2>\n
To the best of my knowledge, Dijkstra\u2019s algorithm only shows up in a few places (There are only two or three that I\u2019m aware of), but it\u2019s vital to understand if you want to play around with graph theory, and if you want to traverse graphs.<\/p>\n
There\u2019s this amazing technology out there that you may have heard of. It\u2019s called GPS technology. Technically GPS refers to the global positioning system. It\u2019s a system of satellites in space that send out radio signals which can be received by any GPS capable device which can then use those signals to calculate the exact latitude, longitude, and height of the device.<\/p>\n
However, when most people think of GPS they think of navigation systems that can give you directions. That\u2019s what we\u2019ll be looking at here. Dijkstra\u2019s algorithm allows us to plan the shortest route from point A to point B.<\/p>\n
The first step in Dijkstra\u2019s algorithm actually comes before we\u2019ve even written any lines of code to implement dijkstra\u2019s algorithm. We need a map. Thankfully there are maps out there that we can download of entire cities that are machine-readable. The idea is simple: take a map and turn it into what\u2019s called a \u201cgraph\u201d.<\/p>\n
A graph (as in the kind from graph theory) is a set of circles (called \u201cnodes\u201d) and lines connecting them (called \u201cedges\u201d). There\u2019s more than one kind of graph. For our example we\u2019ll be looking at graphs that are directed and weighted. Directed means they have arrows instead of just regular lines (sometimes streets are one-way), and weighted meaning that each arrow has a number attached to it to indicate how long the path is, or how much time it will take to get there.<\/p>\n
The edges will be roads, and the nodes will be intersections. For streets that go both ways we can simply set up a second arrow that points in reverse. So for one-way roads there will be one arrow, and for two-way roads there will be two pointing in opposite directions.<\/p>\n
Once we have that our navigation system will figure out which node is closest to where we are, and which node is closest to the destination and have use navigate a short distance to the start, and when we get to the end it will say something like \u201cYour destination is on the left\u201d and then it will cowardly end the trip and not tell us how to get out of the car and walk into the building we\u2019re headed for.<\/p>\n
Getting lost in it<\/h2>\n
So how do we navigate graphs? Up until now everything is fairly simple, but how do you get the shorted path from A to B? When designing an algorithm (or, in our case, understanding one) we need to be able to have some insights into the problem. For example: if we were to magically somehow know that a given node is part of the shortest path from A to B then the shortest path from A to that node is the first part of the trip, and the shortest path from our middle node to B is the second part of the trip.<\/p>\n
If we know the shortest path from the start node to each node on the graph then we\u2019ve essentially solved the problem. We just need to get the path associated with the end node.<\/p>\n
So here\u2019s how we do it. First we\u2019ll create an army of wind-up robots that will go through the graph. Each of these wind up robots will be a data structure which contains two pieces of information: the total distance the bot has traveled so far from the starting node, and the exact path it took. The distance can be an integer or float, and the path variable is a list (or array if you\u2019re brave enough) containing the names of (or pointers to) each node that we\u2019ve traveled along so far in the order we\u2019ve gone.<\/p>\n
Each node is a data structure which has a name of some kind (an integer or string) and an array or list of edges. These edges are each data structures that contain a number (their weight) and a pointer or identifier that points to their destination node. We\u2019ll also tack on two pieces of information to the node structs: the distance we\u2019ve traveled to get there, and the path we took (just like with our bots).<\/p>\n
When a wind-up robot crosses an edge it takes the number from that edge and adds it to it\u2019s internal number, and adds the edge it just crossed to the path variable inside it (this is a fairly obvious thing to do since that\u2019s what traveling along a graph means). Now, assuming that all edges have a positive, non-infinite number associated with them, we should be able to pull off a simple trick: when a bot lands on a new node it will check the number the node has, and if the number on the node is greater than the number the bot is carrying then the bot replaces the number on that node with the one it was carrying. It also does the same with the path variable it had.<\/p>\n
When another bot later finds itself on that node, if the bot had found a shorter path to get there then it will replace the path and number on that node. If it took a longer path then it will be able to tell from comparing the number on the node to it\u2019s number and it will know to backtrack to where it just came from.<\/p>\n
Hopefully some gears are starting to turn in your head. We\u2019ll initialize every nodes\u2019 number to be infinity because all numbers are less than infinity and because floating point numbers can represent infinity as a value (pretty handy here) except for the start node which will be zero. All their paths will initially be empty as well.<\/p>\n
This sounds a lot like a problem involving recursion, doesn\u2019t it? We could write a function that acts as one single bot and it can take in our initial node. It will then call itself once for each edge that node has as it travels along them. It can follow the rules from earlier and after it\u2019s done investigating every top-level edge it should have visited every node enough times to have found the shortest path to that node, and so we should have solved the problem by that point.<\/p>\n
Here’s some pseudo code:<\/p>\n
function dijkstra (distSoFar, pathSoFar, node):\r\n if distSoFar < node.dist:\r\n node.dist = distSoFar\r\n node.path = pathSoFar\r\n for edge in node.edges:\r\n dijkstra(distSoFar + edge.weight, pathSoFar + edge,edge.destNode) <\/code><\/pre>\nAnd that\u2019s how it\u2019s done. Except for a few problems: the first problem is that it doesn\u2019t uses parallelism despite the fact that that seems like it could work here (that\u2019s really a crime in itself). The second problem is that it takes way too long to run. I tried implementing it in Haskell with a dash of parallelism and left it running overnight on a graph of New York city and it wasn\u2019t finished in the morning.<\/p>\n
The Problem<\/h2>\n
The algorithm, as described, isn\u2019t fast enough on large graphs. So what\u2019s the real answer?We have to rethink some things here. First we\u2019ll get rid of putting the path onto each node, and instead store info on what edge it was that took us to that node from the shortest path (thus each node has info on what node came just before it, and what edge was used to get there).<\/p>\n
We\u2019ll also drop carrying the path in each bot, and instead focus on just the distances. Once all is said and done we can work backwards from the end node to build up a path to it. So how can we do all of this more efficiently? This is where priority queues come into play.<\/p>\n
First make a queue that contains pointers to all nodes which are initialized to infinity and have some undefined value for the previous node except, of course, for the start node which will have a distance of zero.<\/p>\n
Then we let our bot loose on the start node. It goes along each edge going out from the node, but doesn\u2019t recurse down the next edges. For each node it meets it decides whether or not to update the distance on that node. The bot will also not accumulate distances anymore and instead will just use the distance from the node it just left and add that to the weight of the edge it traveled along.<\/p>\n
Next we have a list of data structures that point to each node. Most of the nodes still have an infinite distance, but some of them have different finite distances. So we sort the list based on the distances that each node has (or do the smart thing and not call up a sort function every time by simply knowing what nodes to try and move and not checking the entire list) and now the first node in the queue has the shortest distance (the start node since that started with zero).<\/p>\n
Then we remove the first node from the queue. Then for every entry in the queue we do the same. We have a bot travel along from that node along each outgoing edge that node has, update the distances, resort the priority queue, and then drop the first entry in the queue.<\/p>\n
This ensures that we are starting at the start node, and slowly working our way to each adjacent node, and then each node after that, and then the ones after that. On the graph it looks like we\u2019re fanning out from the start node.<\/p>\n
According to Wikipedia we\u2019ll be done either once we reach the end node on the queue or when there are no more nodes in the queue (stopping at the end node seems to be some sort of optimization). The idea is that we\u2019re starting with the node that has the shortest distance each time we look at the priority queue, and updating the adjacent nodes so that they can (possibly) be updated by the node with the shortest path so far.<\/p>\n
The nodes that are updated each round can sometimes be the nodes that were already removed from the queue, and every node will have a chance to update all of their neighbors. All nodes get reached eventually since we\u2019re pulling them from a queue and since we\u2019re always starting with the shortest distances that means every node will be quickly updated with the shorter distances first.<\/p>\n
The nodes that are updated each round can sometimes be the nodes that were already removed from the queue, and every node will have a chance to update all of their neighbors. All nodes get reached eventually since we\u2019re pulling them from a queue and since we\u2019re always starting with the shortest distances that means every node will be quickly updated with the shorter distances first.<\/p>\n","protected":false},"excerpt":{"rendered":"
Recently I started working on a library in Haskell that would implement dijkstra\u2019s algorithm both for fun and for an upcoming project. What I learned is that I didn\u2019t initially understand dijkstra\u2019s algorithm as well as I had thought and many of the explanations out there weren\u2019t very good and often relied on showing an … Continue reading How Dijkstra’s Algorithm Works (The Logic Behind It).<\/span>