Image by Alice O. on Flickr
Learn about the brilliant algorithm behind all of your GPS devices.
Ever wondered how your GPS calculates the shortest route to your destination? The complex algorithms of Google Maps, like most path-finding applications, are based on the famous Dijkstra’s algorithm, invented in 1959 by Dutch scientist and programmer Edsger W. Dijkstra. Although powerful, the logic behind this clever algorithm is deceptively simple!
Getting a Graph
In order to run Dijkstra’s algorithm, our problem needs to be converted into a format that the program can understand. Specifically, we need to create a weighted graph.
In math terms, a graph is a collection of “nodes” connected by “edges”. In a GPS, our edges are roads: paths that lead from one place to another. A node could be a destination (a house, a park, a mall) or it could be anywhere that two edges meet, such as traffic intersections. Using these simple rules, we can represent a city as hundreds of tiny dots (nodes) connected by a web of thin lines (edges).
Each edge has a weight. In our example, this is the time required to travel from one end of the edge to the other, and it depends on many factors including the length of the road, the speed limit, the number of potholes, the presence of construction, etc. Sometimes the shortest path isn’t always the fastest!
In real-life applications, like Google Maps, the information used to determine the weight of an edge is collected in advance from third party providers or customers’ mobile data. However, that only creates an estimate for a single stretch of road. If we want to know how long it’ll take to get across the city, we need to run Dijkstra!
Here’s an example of a simple graph:
Let’s say that we’re starting at node A and going to node E. In a nutshell, Dijkstra’s algorithm explores all possible paths in a clever, non-random fashion, and records distances as it goes. Initially it doesn’t know how long it takes to get to any node, so we say that they’re all “infinitely” far; except our starting node, A, which has a distance of 0.
Imagine that you have a fleet of drones stationed at A. You begin by sending groups out to nodes B, C, and D. Once arrived, the drones check if the total distance travelled (the sum of all the edge weights they’ve flown over) if less than our current estimate for that node. Since all nodes start at “infinity”, the first drone fleet to arrive always sets a new record, but this could be broken by subsequent groups of drones.
Each node keeps track of two attributes:
1) Distance. What is the shortest possible distance between the current node and our starting point? Although it’s called “distance”, depending on the problem the shortest path could actually mean the quickest path, or the easiest path, etc. If you want, you can use “cost” as a more general term instead of “distance”.
2) Previous node. When following the shortest path, which node did the drones fly through directly before arriving at this one?
After updating a node, the drones are going to split into even smaller groups to keep exploring farther and farther until they’ve mapped the entire graph. To keep track of this process in our program, we use a data structure called a priority queue.
A “queue” is a structure similar to a line at a grocery store: the first customer in line is the first customer to be served. A “priority queue” instead mirrors the logic of boarding airplanes. There’s still an element of “first in, first out” to the line, but there’s another, more important order: executives, families, and passengers who need assistance get on the plane before regular passengers.
In a priority queue, the programmer decides what variable is used to determine order. Dijkstra’s algorithm uses the “distance / cost” variable, so that the “closest” node is investigated by drones first. Once visited, we remove the node from the priority queue and toss it in a set. Drones don’t fly over or update visited nodes!
To recap the contents of our program:
- We have a graph of nodes connected by weighted edges
- Each node records its distance from the start point and the previous node in the shortest path
- To help us with our calculations, we use a priority queue full of nodes (sorted by weight)
- We also have an empty set used to record what nodes we’ve visited so that our exploratory drones can avoid them
Let the drones go forth!
The Main Algorithm
The program ends when the priority queue is empty and the set of visited nodes is full.
STEP 1: We pop the first element off the priority queue (referred to as the “current node”). In the first iteration of the algorithm, this is always the start node, since all other nodes are set at a distance of infinity.
STEP 2: Send drones to all adjacent nodes. Record the total distance that each drone travels.
STEP 3: For each neighbouring node, check if we’ve found a new shortest path. If so, update the “distance” and “previous node” variables; this may cause the priority queue to reorder itself.
STEP 4: Add the current node to the “visited” set.
STEP 5: Repeat steps 1-4 for all nodes in the priority queue. In the second round, our “current node” is going to be C, which has a distance of “1” from the start node A. Since A has been visited, the only adjacent node is D.
Remember that when checking the “total distance travelled”, this new fleet of drones is going to sum up the weights of all the edges they’ve flown over. The edge (A, C) has a distance of 1, and (C, D) has a distance of 2, so the shortest distance to the node D is 1+2 = 3. Our priority queue now looks like this:
Once all nodes have been visited and the algorithm finishes, we take our end node and check its “previous node” attribute. Hopping backwards from previous node to previous node, we unwind the trail back to the start node and presto! We have the shortest path.
In this example, the best route is A, C, D, E, with a total distance / cost of 7.
1) How does the algorithm know which nodes are neighbours? Most likely, the program uses a data structure like an adjacency list or an adjacency matrix, created at the same time as the nodes and edges.
2) It’s possible to store the “distance” and “previous node” variables in separate lists (or even dictionaries) rather than keeping them with the node. This choice often boils down to the language you use to implement Dijkstra’s algorithm. With an object-oriented language like Java, it’s preferable to keep variables inside objects, while something more flexible like Python might benefit from using separate data structures.
3) If there are two equally short paths, the one detected first is the one presented to the user. A sophisticated app would probably check for cases like this, and suggest both options.
Also note that Dijkstra’s algorithm doesn’t work on graphs with negative values. In a GPS, of course, this makes perfect sense — how could you travel down a road in negative time? However, this limitation does mean that Dijkstra’s algorithm is only suitable to problems that can transformed into graphs with positive edges.
Which are numerous! Routing data packages through a network (i.e. sending messages over the internet or calling someone’s phone), suggesting connections in a social network, and modelling the spread of infectious diseases are all applications for this cool algorithm.
Want to give it a go ? Grab a pencil and paper, or open up your favourite IDE, and use Dijkstra’s algorithm to find the shortest path from A to G:
In this case the graph is fairly small, so you could probably figure out the answer without Dijkstra. But when a graph has millions or billions of nodes, and exponentially more edges, it’s a relief to have a handy algorithm in your back pocket to tackle just such a problem!
A, B, D, F, G. Total distance of 13.
Computerphile Video Tutorial: Dijkstra’s Algorithm
Detailed (but accessible) article about the technical details behind Dijkstra’s algorithm
Article about graph representation
Pseudocode for Dijkstra’s algorithm
Python code for Dijkstra’s algorithm
Also In The October 2018 Issue
Create a fun adventure game with sprites using a retro fantasy computer.
Hide information in plain sight using a clever code and a good book.
Logic puzzles help develop reasoning skills useful for programming, computer science, and anything you might do.
Find perfect and fun gifts for your loved ones that teach STEAM concepts and skills.
From light-up bow-ties to conductive thread, you’ll be the life of the party with this STEAM-inspired gear.
A free online test service reveals how much personal data your web browser is giving away.
Add more tools to your command line arsenal, including running mini-scripts and making backup copies.
Use switches to take your robotic creations to the next level.
Create the American flag in SketchUp using this detailed tutorial.
From lasers to supernovas, Berboucha is making science communication a priority.
Code can always be improved. Check out these tips to make you the best programmer you can be!
It’s a programming language unlike any you’ve seen before. Check out this symbolic system designed for mathematical calculations.
It’s a game that’s obsessing the world. Harmful, or a potential gateway to new skills?
Some fun Python code that introduces you to the arcane world of event handling.
New, improved, faster, and sleeker - it’s Scratch 3, your new favourite block language!
Learn about the brilliant algorithm behind all of your GPS devices.
It’s free, comprehensive, and available on-the-go. This cool app helps you master Python faster than ever before.
Open up whole new worlds to explore through these interesting, diverse add-ons.
Links from the bottom of all the October 2018 articles, collected in one place for you to print, share, or bookmark.
Interesting stories about computer science, software programming, and technology for October 2018.