Dijkstra’s Algorithm In Swift
A Dive into Graph Theory and Swift
Hi! This post has moved to a new blog! Come to fivestars.blog for the latest articles!
If you’ve ever heard of the term Graph Theory, surely you’re acquaintance with the Dijkstra’s Algorithm.
If you’re not, it’s all right! This article includes everything you need to know.
This chapter will bring you up to speed on what Graph Theory and the Dijkstra’s Algorithm are.
If you’re confident enough, you can skip this part! (🚀 jump to the Swift Time! chapter)
See the picture at the top beginning of the article? This is a what in Mathematics and Computer Science we call a Graph.
The circles are called Nodes (or vertices) and they represent the graph entities (more on this later) while the lines connecting the nodes are called Connections (or edges).
These connections, which always connect two nodes, are mainly of two types: bidirectional and mono-directional.
The former means that the connection works in both ways (duh!), while the latter means that the connection exists only from one node to the other, but not vice-versa (you will need a second connection to go the other way around).
These simple concepts have huge applications all over the world and you are probably using them all the time!
Real World Examples
Bidirectional Graph: Facebook
Let’s visualize your Facebook friends Graph!
You might end up with something like this:
In this graph each node is a person, and each (bidirectional) connection represents the friendship between these people.
“Coincidentally” Facebook has a developer API called Graph.
Mono-directional Graph: Twitter
If we take a look at our followers on Twitter, the result might be something like this:
In this case each node is a Twitter Account, but the connections now are mono-directional, because if I follow you, this doesn’t imply that you are following me back.
Now that we understand what a Graph is, let’s talk about one of its hottest topics: the Shortest Path Problem.
This challenge is super simple to understand: given two nodes in one Graph, find the shortest way to go from one node to the other (if it exists).
For us it’s a simple game (like solving a maze), but for a machine it’s a challenge that has to be solved as quick as possible.
Again, this is something that you’re using all the time, just think about how the Apple Maps App computes the best route, or how LinkedIn determines that a profile is a first/second/third level connection from you.
One of the most famous (dare I say, THE most famous) Shortest Path Finder Algorithm is Dijkstra’s Algorithm, which is based on three steps:
- Find the cheapest unvisited node reachable
- Mark it as visited and keep track on which nodes you can visit from it
The algorithm ends as soon as we reach the destination node, or whenever there are no more reachable nodes.
When I say cheap I mean the node that costs less to reach from all the nodes we’ve visited so far.
This cost comes from the connections: sometimes the graph connections are equal (like the Facebook friendships, there’s no difference between one connection and another) but sometimes they differ: if you have two ways to go to your home, one way might be easier/cheaper, than the other because on the latter you may have to climb a mountain or something.
Now that we’re all up to speed, let’s implement everything in Swift!
The Node class will be nothing more than a property (used by the algorithm) to see if we’ve visited it already, and an array of connections to other nodes.
As seen in the Node definition, each connection is assigned to a specific node, therefore all we need to define inside the connection itself is its weight (also known as cost) and the node it connects to.
I’m obviously using the mono-directional connections, this way it’s easier to manage both bidirectional and mono-directional Graphs.
Lastly we need define a path: a path is nothing more than a successions of nodes.
This will help us keeping track which paths in our graph we’ve already visited and how we got there.
More importantly, our algorithm will return us this entity to describe the shortest path between our challenge source node and destination node.
We will use a recursive way for this definition:
For convenience, I’m also adding a
cumulativeWeight property to keep track on the cost to reach the path’s node: this cost is the sum of all the connections weights that we have traveled from the source node to this node.
Everything is set! Let’s dig into the algorithm:
Firstly we define the
frontier is a collection of paths to nodes that can reach from the nodes the we’ve visited so far.
It’s initially empty, but as soon as we launch the script we will add a path to our start node (line
We can now start following the Dijkstra’s Algorithm steps:
1. Find the cheapest unvisited node
To do so we extract the cheapest path from our frontier (line
9), check if the node was not visited yet and, if it is not, we proceed to the next step (line
2. Mark it as visited and keep track on which nodes you can visit from it
As soon as we reach this step we make sure to mark our node as visited (line
16), and then we add all the new (unvisited) reachable nodes from this node by exploring its connections (lines
while cycle is now complete, therefore we really just repeat the two steps above!
As you may have noticed, we do something between step 1 and 2 (line
we check if the new cheapest node is our destination node: if it is, congrats! 🎉 We’ve completed the algorithm! Otherwise we continue to step 2.
The algorithm may return an optional (line
22): it is possible that the source and destination nodes don’t have a path that connect each other.
👾 Swift Playground
All right! We’ve now everything we need to play with the Dijkstra algorithm in Swift! Here’s the Playground with an example at the bottom.
In the academic world there are discussions on whether Graph Theory should replace Geometry in our schools curriculum: as a Computer Engineer myself, I can see why this might happen in the future 😁.
I hope you’ve learn something new today! Till next time 👋🏻
⚠️️ Note️ ⚠️️
Some readers have pointed out that the
frontierarray is not the most efficient approach to obtain the cheapest available path, because of its sorting overhead.
I agree, there are better ways: for example by using Priority Queue data structure.
Thanks to u/madiyar and Ilya Myakotin for the support!
📢 Announcement! 📢
My blog is moving out of Medium! Please sign up here to be notified when the new blog will launch! Thanks 🤗
Federico is a Bangkok-based Software Engineer with a strong passion for Swift, Minimalism, Design, and iOS Development.