Dijkstra’s Algorithm In Swift

A Dive into Graph Theory and Swift

Federico Zanetello
Aug 22, 2017 · 6 min read

Quick Introduction

This chapter will bring you up to speed on what Graph Theory and the Dijkstra’s Algorithm are.

Graph Theory

See the picture at the top beginning of the article? This is a what in Mathematics and Computer Science we call a Graph.

Real World Examples

Bidirectional Graph: Facebook
Let’s visualize your Facebook friends Graph!
You might end up with something like this:

Picture from Mathematica StackExchange.
Picture from Social Media Research Foundation.

Dijkstra’s Algorithm

Now that we understand what a Graph is, let’s talk about one of its hottest topics: the Shortest Path Problem.

Picture from Linkedin.
  1. Mark it as visited and keep track on which nodes you can visit from it
  2. Repeat

Swift Time!

Now that we’re all up to speed, let’s implement everything in Swift!

Node

Connection

Path

Lastly we need define a path: a path is nothing more than a successions of nodes.

The Algorithm

Everything is set! Let’s dig into the algorithm:

Yup, just 23 lines of code.

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 10).

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 18–20).

3. Repeat

The while cycle is now complete, therefore we really just repeat the two steps above!

👾 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.

Conclusion

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 😁.



Swiftly Swift

Write code swiftly

Federico Zanetello

Written by

Swiftly Swift author, building apps @kimchi_media .

Swiftly Swift

Write code swiftly