Side Projects
My Read

Recent Posts
Recent Comments
 atdhe on CakePHP URL Shortener Service Tutorial
 voidet on Dijkstra’s Shortest Path Algorithm in Swift
 Fred on Ultimate Guestbook Tutorial: How to build a Guestbook with a honeypot, error checking, IP banning, pagination, email notification and smilies with PHP and mySQL
 Florian on Dijkstra’s Shortest Path Algorithm in Swift
 Pete Everitt on Parts: iOS Bike Maintenance via Strava
Archives
 March 2015
 December 2014
 July 2014
 April 2014
 March 2014
 February 2014
 January 2014
 December 2013
 October 2013
 September 2013
 February 2013
 December 2012
 September 2012
 July 2012
 January 2012
 September 2011
 August 2011
 February 2011
 January 2011
 November 2010
 October 2010
 August 2010
 June 2010
 May 2010
 April 2010
 March 2010
 February 2010
 January 2010
 November 2009
 October 2009
 September 2009
 August 2009
 July 2009
 June 2009
 April 2009
 March 2009
 February 2009
 January 2009
 December 2008
 November 2008
 October 2008
 September 2008
 August 2008
 July 2008
 June 2008
 May 2008
 April 2008
Categories
Meta
Dijkstra’s Shortest Path Algorithm in Swift
December 9, 2014,
1,604 views
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:
1 2 
A  B  D \ C / 
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 
struct Edge { var distance:Double var destinationVertex:Vertex } struct Graph { var vertices:[Vertex] } class Vertex:Hashable { var key:String? var neighbours:[Edge]? var hashValue:Int { get { return key!.hashValue } } init(){} convenience init(key:String) { self.init() self.key = key } func distanceToVertex(targetVertex:Vertex) > Edge? { return self.neighbours?.each({ (edge:Edge) > Edge? in if (edge.destinationVertex == targetVertex) { return edge } return nil }) } } func == (lhs:Vertex, rhs:Vertex) > Bool { return lhs.hashValue == rhs.hashValue } 
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 nonreturning function is kind of something annoying, I do hope to find a more elegant solution, so please forgive me for now.
1 2 3 4 5 6 7 8 9 10 11 12 13 
extension Array { func each<U>(closure:(T)>U?)>U? { for i in self { var returnVal = closure(i) if (returnVal != nil) { return returnVal } } return nil } } 
Our setup
Next is our graph. Below is the setup that represents the above problem:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
var a = Vertex(key: "A") var b = Vertex(key: "B") var c = Vertex(key: "C") var d = Vertex(key: "D") a.neighbours = [ Edge(distance: 2, destinationVertex: b), Edge(distance: 4, destinationVertex: c) ] b.neighbours = [ Edge(distance: 1, destinationVertex: d) ] c.neighbours = [ Edge(distance: 5, destinationVertex: d) ] var graph = Graph(vertices: [a, b, c, d]) var paths = dijkstra(graph, d) 
The Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
func dijkstra(graph:Graph, target:Vertex) > [Vertex:Vertex] { var queue = graph.vertices var distances:[Vertex:Double] = [:] var previousPaths:[Vertex:Vertex] = [:] var currentVertex:Vertex = queue[0] queue.each { (element:Vertex) > Void? in distances[element] = Double.infinity previousPaths[element] = nil return nil } distances[currentVertex] = 0 while (queue.count > 0) { var closestNode:Vertex? = nil var distance:Double = Double.infinity queue.each({ (vertex:Vertex) > Void? in if (closestNode == nil  distance < distances[vertex]!) { distance = distances[vertex]! closestNode = vertex } return nil }) if (closestNode! == target) { return previousPaths } var nodeIndex:Int? = find(queue, closestNode!)? queue.removeAtIndex(nodeIndex!) if (closestNode?.neighbours != nil && closestNode?.neighbours?.count > 0) { closestNode?.neighbours?.each({(neighbour:Edge) > Void? in var distance = distances[closestNode!]! + closestNode!.distanceToVertex(neighbour.destinationVertex)!.distance if distance < distances[neighbour.destinationVertex] { distances[neighbour.destinationVertex] = distance previousPaths[neighbour.destinationVertex] = closestNode! } return nil }) } } return previousPaths } 
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
var source = a var target = d var graph = Graph(vertices: [a, b, c, d]) var paths = dijkstra(graph, d) var pathVertices:[Vertex] = [target] var child = target while (child != source) { child = paths[child]! pathVertices.append(child) } var pathString:[String] = reverse(pathVertices).map { (vertex:Vertex) > String in return vertex.key! } println(" ~> ".join(pathString)) 
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
Categorised under ios
2 Comments
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 ?
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