Swift Algorithm Club: Swift Dijkstra’s Algorithm

Ross O'Brien

Swift Algorithm Club: Swift Dijkstra's Algorithm

The Swift Algorithm Club is an open source project to implement popular algorithms and data structures in Swift.

Every month, the SAC team will feature a cool data structure or algorithm from the club in a tutorial on this site. If your want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll learn how to implement a Swift Dijkstra’s Algorithm: an algorithm for finding the shortest path between nodes in a graph.

This Swift implementation was first created by Taras Nikulin, and is now refactored for a tutorial format.

This tutorial assumes you have read these three tutorials first (or have equivalent knowledge):

Note: New to the Swift Algorithm Club? Check out your getting started post first.

Getting Started

Edsger W. Dijkstra developed an algorithm for finding the shortest path through a graph in 1956, and demonstrated its use by navigating a simplified map of the Netherlands. This became known as Dijkstra’s Algorithm, and you’ll learn how to implement it in Swift in this tutorial.

In our previous tutorial on breadth-first search path-finding, our hero Wenderlink was exploring a maze of monsters and wonders, and needed to find a route from room to room from the entrance to a great treasure.

In the tutorial, you implemented a Swift algorithm which found him a path. Better than that, because your search always explored the nearest rooms first, you knew that any route you found would also be the shortest possible route.

However, you only knew this because the distance between any two rooms was always the same. If you only want to measure distance in rooms, then your algorithm finds the route which travels through the fewest number of rooms.

In this tutorial, the devious dungeon creator has extended the corridors between rooms. Some corridors are short, and others are long.

Now, if there are two routes to the treasure, it’s possible that the route through the fewest rooms is actually not the shortest.

But really, that doesn’t change your approach very much. In the breadth-first search, you always explored the nearest rooms first. In Dijsktra’s Algorithm, you do the same, but you prioritise your search differently.

Note: In this tutorial you are using distance to describe the quality you want to minimise, but if you want to use this algorithm in other contexts then other qualities work just as well.

For example, in the context of dungeon exploration a ‘high distance’ could mean a task that takes a long time, or a corridor that contains many obstacles or enemies to defeat. What’s important is this quality is non-negative and that lower is better.

How Dijkstra’s Algorithm Works

Let’s walk through how Dijkstra’s Algorithm’s works by looking at this example.

First your hero explores the entrance room, in case that’s where the treasure is.

If it’s not there, he determines all the rooms which are connected to the entrance room, and prioritises them by distance, shortest first.

He then explores the nearest room to the entrance for the treasure.

If it’s not there, he determines all the rooms connected to that room, prioritises them by their distance from the entrance room, and adds them to the priority queue.

The next nearest room to the entrance room gets explored in turn, with a few differences from other algorithms:

  • Unlike breadth-first search, it doesn’t have to be an unexplored room connected to the entrance.
  • Unlike depth-first search, it doesn’t have to be an unexplored room connected to the current location.
  • It’s simply the highest priority room in the search, as measured by its distance from the entrance room.

The next nearest room gets explored. This time he finds an alternative corridor to a room already on his priority list. The alternative route is shorter than the route already prioritised, so you update the priority – meaning you’ll explore that room much sooner. If the alternative route was longer, though, you keep the original priority.

You keep exploring until the treasure room becomes the highest priority room – via the shortest possible route from the entrance – or until you run out of rooms, determining that there is no treasure to be found.

Swift Dijkstra’s Algorithm

Start by downloading the starter playground here. The project contains a Swift 4 playground, including data structures from previous tutorials (updated for Swift 4).

We’re going to extend the Graphable protocol from the Adjacency-List Graphs tutorial, so in your Playground file, type this:

extension Graphable {
  // you'll write some code here soon!
}

Our strategy is actually going to be very similar to how you handled the Breadth-First Search, so let’s revise how you did that.

A graph is a network of vertices and edges, but when we’re calculating the shortest path from one vertex to any other, not all of the edges will be part of that shortest path. So we’re going to create a tree, whose root vertex is where you start the path.

Every vertex in the tree is a vertex which is reachable from the root vertex in the graph. Every edge in the tree is the last edge in the shortest path from the root vertex to the edge’s destination vertex. The edge’s source vertex will also have an entry in the tree, so to get the shortest path to any vertex, you just follow the edges back to the root. There’s always exactly one path, and it’s always the shortest path.

For this you created an enum type Visit, to represent the direction back to the root vertex. (This already exists in the playground, so you don’t need to create it.)

public enum Visit<Element: Hashable> {
  case source
  case edge(Edge<Element>)
}

There are two states for a Visit; either this vertex has an edge back to another vertex, and you keep going back, or it is the root vertex, and you stop.

Our tree is going to take the form of a dictionary of type [Vertex : Visit]. Every Vertex in the tree has a Visit state to tell us where to go.

Note: This is quite a fragile data structure, in this form! We’re making the enormous assumption that the tree is correctly structured. If there’s a Vertex in this tree, and the tree has an Edge for that Vertex, then we’re assuming that the edge’s destination is that Vertex, and the edge’s source is also in the tree. If we’re mistaken about this then the whole algorithm falls apart. So, we’re going to construct the tree very carefully.

If you wanted to, of course, you could build a much more robust version of this data structure, perhaps with throws and try statements and so on to keep everything safe, but right now that would make this tutorial too long so we’re going to keep things simple. :]

You’re going to need to ask your tree for information, so you’re going to write a function which takes a tree and a given destination vertex, and returns the path from the tree’s root to the destination.

In the playground file, inside the protocol extension, type this:

public func route(to destination: Vertex<Element>, in tree: [Vertex<Element> : Visit<Element>]) -> [Edge<Element>] { // 1

  var vertex = destination // 2
  var path : [Edge<Element>] = [] // 3

  while let visit = tree[vertex],
    case .edge(let edge) = visit { // 4

    path = [edge] + path
    vertex = edge.source // 5
  }
  return path // 6
}

Let’s review what you’ve just done.

  1. You wrote the function signature. As intended, this function takes a Vertex and [Vertex: Visit] dictionary tree and returns an array of Edges.
  2. You created a variable to represent the ‘current’ Vertex in the tree. Initially this is the destination vertex, but this will change.
  3. You created a variable to store the path of edges from the tree’s root to the destination. Initially this is an empty array.
  4. You created a while-loop to gather up the edges. The loop tests that there is a Visit entry in the tree for the ‘current’ Vertex, and that this entry takes the form of an edge. When this test fails, the loop ends.
  5. You added the edge to the beginning of the path, and set vertex to the edge’s source Vertex, moving one step closer to the root
  6. With the loop ended, you returned the array of edges from the function.

So far, so good. Now, when you implemented Breadth-First Search, you could also use the count property of the edge array to tell us how long the path was, in terms of the number of rooms passed through. In Dijkstra’s algorithm you need to measure the distance differently.

For this we’re going to use the weight quality of the edges. In the Adjacency List tutorial the weight is represented by a Double?, because some edges might be weight and some might not. you’ll be assuming that all edges which make up part of a route will be weighted.

Under the route function you’ve written, type this:

public func distance(to destination: Vertex<Element>, in tree: [Vertex<Element> : Visit<Element>]) -> Double { // 1
  let path = route(to: destination, in: tree) // 2
  let distances = path.flatMap{ $0.weight } // 3
  return distances.reduce(0.0, { $0 + $1 }) // 4
}

Let’s review what you’ve just done.

  1. As before, you’ve written the function signature. This function takes a Vertex and [Vertex: Visit] dictionary tree and returns the distance traversed on the path from tree source to destination as a Double.
  2. You call the route function you wrote earlier to get the list of edges in the path.
  3. You flatMap each edge into its weight. If an edge’s weight should somehow be nil, that edge is quietly ignored here.
  4. You reduced the array of distances to their total (assuming a path with no edges has 0.0 distance, and then adding the weight of each edge in the path in turn).

So, if you can just generate a tree from the graph, you can generate the shortest path and determine its overall length. Let’s do that now!

Generating the Tree

After the distance function, type this:

public func dijkstra(from source: Vertex<Element>, to destination: Vertex<Element>) -> [Edge<Element>]? {
  // you'll be writing code here
  return nil
}

This is your main ‘Dijkstra’ function. Given a source and destination Vertex, return the shortest path, if there is one.

Immediately inside the function, add this line to create the Vertex : Visit tree:

var visits : [Vertex<Element> : Visit<Element>] = [source: .source]

You ‘pre-load’ this with the source vertex and the Visit.source state.

Then you need to create a queue of vertices to explore. We’re going to be prioritising these vertices based on distance from the source vertex, so here’s where we’re going to use the Priority Queue data structure. Under the declaration of visits, add this:

var priorityQueue = PriorityQueue<Vertex<Element>>(sort: { self.distance(to: $0, in: visits) < self.distance(to: $1, in: visits) })
priorityQueue.enqueue(source)

Here you've created a PriorityQueue which sorts vertices, initialised with a closure which uses the distance function you've written to sort the vertices by distance. Then you enqueued the source vertex as the first vertex to explore.

Below that, type this to begin exploring the graph:

while let visitedVertex = priorityQueue.dequeue() { // 1
  if visitedVertex == destination { // 2
    return route(to: destination, in: visits) // 3
  }
  // Code for goal state not reached
}

Here's what you've done:

  1. You dequeued the first element from the priority queue, and called it visitedVertex.
  2. You checked whether the visited vertex is the destination.
  3. If the visited vertex is the destination, you returned the route from the source vertex to the destination vertex, as determined from the visitstree.

If the visited vertex isn't the destination vertex, we're going to explore the vertex and add its neighbours. Replace the 'Code for goal state not reached' comment with this:

let neighbourEdges = edges(from: visitedVertex) ?? [] // 1
for edge in neighbourEdges { // 2
  if let weight = edge.weight { // 3
    // Code for adding the neighbour vertex
  }
}

Let's review this code:

  1. You're getting the list of neighbouring edges for the visited vertex, or creating an empty list if there aren't any.
  2. You're iterating through that list of neighbouring edges. If there aren't any, there'll be no iterations here.
  3. You're testing if the neighbouring edge has a weight value. This will be important in a moment.

There are two reasons to enqueue a neighbouring vertex. The first is that we've never encountered them before, and the second is that you have encountered them before but you have a shorter, higher-priority route for them. If we've encountered the vertex before but we've found a longer route to it than you have already, you want to ignore the new route.

Because of these reasons, now that you have a weighted edge to a neighbouring vertex, there's a little bit of duplication here in deciding to enqueue that vertex. Replace the 'Code for adding the neighbour vertex' with this:

if visits[edge.destination] != nil { // 1
  if distance(to: visitedVertex, in: visits) + weight < distance(to: edge.destination, in: visits) { // 2
    visits[edge.destination] = .edge(edge) // 3
    priorityQueue.enqueue(edge.destination) // 4
  }
} else { // 1
  visits[edge.destination] = .edge(edge) // 3
  priorityQueue.enqueue(edge.destination) // 4
}

Let's review this code:

  1. You tested whether the visits tree already has an entry for the current vertex's neighbour. If there's no entry, you're going to enqueue this vertex.
  2. If there is an entry, you test if the distance to the current vertex, plus the weight, would be less than the distance the priority queue is already using to prioritise the neighbour.
  3. You created, or overrode, the entry in the visitstree for the neighbour. The tree will now use this entry to prioritise the vertex.
  4. You added the neighbour to the priority queue.

And that's it! Congratulations - you've implemented Dijkstra's Algorithm in Swift.

Testing it Out

Now let's test it out. Add the following to the bottom of your Playground:

let dungeon = AdjacencyList<String>()

let entranceRoom = dungeon.createVertex(data: "Entrance")
let spiderRoom = dungeon.createVertex(data: "Spider")
let goblinRoom = dungeon.createVertex(data: "Goblin")
let ratRoom = dungeon.createVertex(data: "Rat")
let treasureRoom = dungeon.createVertex(data: "Treasure")

dungeon.add(.undirected, from: entranceRoom, to: spiderRoom, weight: 11)
dungeon.add(.undirected, from: spiderRoom, to: goblinRoom, weight: 11)
dungeon.add(.undirected, from: goblinRoom, to: treasureRoom, weight: 11)
dungeon.add(.undirected, from: entranceRoom, to: ratRoom, weight: 31)
dungeon.add(.undirected, from: ratRoom, to: treasureRoom, weight: 12)

dungeon.description


if let edges = dungeon.dijkstra(from: entranceRoom, to: treasureRoom) {
  for edge in edges {
    print("\(edge.source) -> \(edge.destination)")
  }
}

You should see it print out the shortest path to the treasure thanks to Dijkstra's algorithm:

Entrance -> Spider
Spider -> Goblin
Goblin -> Treasure

There are some interesting implications of this code, particularly if compared to the Breadth-First Search implementation. In that algorithm you tried to reduce the work done by the algorithm by ensuring that a vertex could only be enqueued once.

This was a simple effort because vertices never changed priority in that algorithm - if a vertex exists in the queue, then it is already at its nearest position to the source vertex as measured by number-of-vertices-distance, and will never get nearer.

However, in Dijkstra's algorithm, shorter routes can be found during the exploration, so vertices often need to be prioritized higher in the queue. However, in this implementation, while enqueuing the vertex again does put it into the correct position in the priority queue, it does create a duplicate entry in the priority queue, and the duplicate entry can remain at it's higher-distance, lower-priority position in the queue.

The same vertex can be dequeued several times. However, this doesn't create complications because the vertex's neighbors will have already been enqueued at their shortest distance, and won't be enqueued again.

Where To Go From Here?

I hope you enjoyed this tutorial on Dijkstra's Algorithm in Swift!

You’ve extended the behavior of all Graphable data types, so you can search for a route from any vertex to any other vertex, and you can be sure it has the shortest distance.

Here is a playground file with the above code. You can also find the original implementation and further discussion in the Swift Dijkstra's Algorithm section of the Swift Algorithm Club repository.

This was just one of the many algorithms in the Swift Algorithm Club repository. If you're interested in more, check out the repo.

It's in your best interest to know about algorithms and data structures - they're solutions to many real world problems, and are frequently asked as interview questions. Plus it's fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing Dijkstra's Algorithm in Swift, please join the forum discussion below!

Note: The Swift Algorithm Club is always looking for more contributors. If you've got an interesting data structure, algorithm, or even an interview question to share, don't hesitate to contribute! To learn more about the contribution process, check out your Join the Swift Algorithm Club article.
Ross O\'Brien

Ross snuck into the world of iOS development in 2010, and hasn't been thrown out yet. He's a keen Swift developer, enjoys board gaming and ceilidh dancing, and would absolutely love a cup of tea, milk no sugar ta, thank you for offering.
He currently works near Manchester, UK.

Other Items of Interest

Save time.
Learn more with our video courses.

raywenderlich.com Weekly

Sign up to receive the latest tutorials from raywenderlich.com each week, and receive a free epic-length tutorial as a bonus!

Advertise with Us!

PragmaConf 2016 Come check out Alt U

Our Books

Our Team

Video Team

... 20 total!

iOS Team

... 74 total!

Android Team

... 30 total!

Unity Team

... 12 total!

Articles Team

... 14 total!

Resident Authors Team

... 25 total!

Podcast Team

... 7 total!

Recruitment Team

... 9 total!