beanz Magazine

Dijkstra’s Algorithm

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!

Initializing Values

Here’s an example of a simple graph:

Become a subscriber and get access to the rest of this article. Plus all our magazine articles.

Stories also include numerous links to help parents, kids, and teachers learn more. Get access today at just $15 per year for online magazine only or $29.99/year for print + online ($35/year outside US)!

Subscribe Today!

Also In The October 2018 Issue

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.

An old classic with a electronic twist, featuring JavaScript and micro:bit.

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.

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.