# Dijkstra’s Algorithm In Swift

## A Dive into Graph Theory and Swift

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

You might end up with something like this:

## Dijkstra’s Algorithm

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

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!

## 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:

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

Written by