Dijkstra’s Shortest Path Algorithm in Swift

Dijkstra’s Shortest Path Algorithm in Swift

If you read my previous post you may of read that I am doing a fair amount of skilling up in the algorithm department. I thought I would never to go back to the books but after doing so it’s opened my mind up to many possibilities of polishing up my own apps, I highly recommend you do the same. Anyhow, I came across Dijkstra’s shortest path algorithm, to, you know, find the shorted path on a network/graph.

How it works

The algorithm itself is pretty simple, as in not many line of code and no crazy mathematical formulas. The key principle is that shortest paths are recorded incrementally against nodes themselves. A dictionary is used to keep track of neighbouring node’s nearest neighbour. To illustrate let’s try a very basic graph:

From “A” we can get to “D” via C and B. Let’s say the shortest path is A – B – D. The flow would go something like this:

  • Look at A’s neighbours and find the shortest path. It’s B
  • In the dictionary we write this as B is the quickest route from A. So “A” => “B”
  • Next we look at C being nearest neighbour. It’s value is “C” => “A”, meaning the shortest way so far to get to C is through A.
  • Next up we look at B again. We find that it can get to “D” and as D hasn’t been discovered yet we mark it as “D” => “B”.
  • Finally we look at “C” again, we find that it’s total path (the value stored on C plus the distance needed to get to D) is greater than that of A – B – D. So we don’t store anything against D as it already has a smaller value.

Our Swift Models

Below are our structures and classes to setup a graph. A graph is a collection of Vertices and edges. Our vertices and their neighbours will be connected by edges. So a Vertex has many Edges and a graph has many Vertices. If you haven’t played with hashmaps yet in swift take a look! This is so we can store our objects as keys in our dictionaries. A must have here.

Extensions

To make life a bit easier we’ll be using an extension that will allow us to call .each on our arrays of which will pass in a value and allow us to bail out of the each loop if need be. Would could also do “for element:Vertex in vertices” but we want to play with extensions. The nil check and nil at the base of a non-returning function is kind of something annoying, I do hope to find a more elegant solution, so please forgive me for now.

Our setup

Next is our graph. Below is the setup that represents the above problem:

The Implementation

A quick summary of this:

  • We setup our graph as a scorecard we need to fill in as we go. We set all the observations to infinity lengths and clear the previous paths to nil
  • Next we set the current vertex to be our source (the first one in the list) then we set it’s default distance to be 0. This is crucial for this algorithm to work.
  • Next up we start our while loop until our queue is empty. A queue is ordered remember, breadth first. So it will start at our source the look as shallow as possible
  • It starts from the closest node then looks at it’s neighbour. In our case it starts from A (the closest node) and then moves to B as it is a neighbour. It then looks at the distance between A and B, and also A’s distance marking (which was 0). If this new distance is lower than what we already have for the neighbour then mark it as an observation for B and add it’s distance. This is true as B’s distance is already Infinity.
  • We then look at B, as its next on the queue. We look at its neighbours who have not yet been observed which is only D, we record its distance against D between B (we have see A, it’s removed off the queue). It does the same cycle.
  • Next on the stack is C. Nothing recorded yet for C, so we use its distance
  • Last on the queue is D. It’s distance is already in the system, but we check if the total distance for A + C + D is less than what is already stored against D. It isn’t so we leave it alone
  • All done so we return previous Paths, which will look like the key’s of. A, B, C

Printing our Path

To print it we look at the output from the paths array. They are pointers to the smallest nodes and their parent nodes.

What does this do? It kicks off our function with our graph. Result are the nodes with pointers. We can then start from our target, or end of the path, and work backwards. Since we’ve set pointers to the cheapest/shortest path against the node this allows us to iterate all the way back to the start just using the pointers to hop from one object to the next.

We then write a map function to get all the nodes in our shortest path and output the key. Then join with a nice squiggly tilde key to make things pretty!

I hope this has helped you in life 🙂

Playground

If you want to play through the code in the playground feel free to grab the playground Dijkstra.playground

Posted by voidet

Categorised under ios
Bookmark the permalink or leave a trackback.

2 Comments

  1. Hello, thanks for this great help !
    I tried your code in playground, everything worked just fine,
    but in my app code, the same code gave me an error !
    Here it is :
    “unexpectedly found nil while unwrapping an Optional value”
    for this lines :
    ” child = paths[child]!”
    in :
    while (child != source) {
    child = paths[child]!
    pathVertices.append(child)
    }

    Can you help me with this, please ?

    May 7, 2015 @ 8:42 am
    • voidet

      Looks like there was a nil coming out of paths for the child node. Trace it back to find where child is nil and figure out why we’re storing a nil value for child

      June 23, 2015 @ 5:14 am

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

or