Shortest route using Dijkstra

The cycling and walking networks in my apps are node based. Each node has a number and every node is linked to one or more other nodes. In real life these nodes are signs by the road. On such a sign the node number is mentioned and the numbers of the connecting nodes are mentioned often with direction arrows.

When a node is tapped on a device the app shows the connected nodes with dotted lines. These connected nodes can then be tapped and you repeat this process until you’ve got yourself a walking or cycling route.

The advantage of tapping these nodes one at a time is that you have great control over your route as you can steer your route in any direction at any time. The downside is that the creation of longer routes require a lot of taps. Say that you want to ride from Ghent to Antwerp, that’ll take you some time and some tappin’.

Last year I added functionality where users can tap two non-connected nodes and the app then calculates the shortest route between the two. I used recursion to find the shortest route. As you can imagine recursion isn’t ideal for that sort of thing. It works, but I noticed that 12 levels of recursion seems to be the maximum. Any deeper than that and the calculation takes too much time.

As a result the app has to spit out ugly “The distance between these 2 nodes is too long” messages every now and then. Still, it was a good step forward and a nice stop-gap solution until something better was found.

Dijkstra

While I was working on this recursive solution someone mentioned Dijkstra algorithm on Twitter. I had a quick look in Google but it seemed a bit too complex at the time. I wanted to move faster and deliver a big step forward to my users, even though it wasn’t ideal.

The first time I played with the Android version of the app the developer mentioned Dijkstra as well. It was in the Android app and it worked very well. I could tap a node near the Belgian coastline, tap another node near Germany and the app would calculate the shortest route between nodes more than 300km apart, and it did it in no time. Very impressive stuff!

I knew then that I would have to take some time to revisit the algorithm and bring the iOS apps up to speed, to deal with this problem once and for all.

Implementation

Dijkstra is a non-recursive algorithm that marks the nodes it has travelled as visited and uses a concept called tentative distances to calculate the shortest path. I spent some time searching the internet and found a couple of websites that explain the algorithm in human language.

My apps have a pretty good object model. I feel I’ve reached a nice balance between having just-enough data in memory combined with quick lookup tables in case I need more information. As a result the apps run fine on devices like the iPhone 4s or the original iPad mini.

To implement the Dijkstra algorithm I had to make a few changes to the model. The memory footprint is still very low but I’ve made more use of lookup tables. Basically the model has been cleaned up so that node connections can be found faster.

Usually when I implement something new, it goes something like this:

• Read and understand half the algorithm
• Write code, run it, see it doesn’t work
• Revisit the algorithm, read a bit more, followed by an “a-ha” moment
• Dive into the code again
• Repeat

This time I did things differently. I used 2 or 3 different websites that explained the algorithm and a lot of paper to jot down notes, even reworking the object model — on paper — to truly understand how the algorithm worked and what the code impact would be.

Once I had a pretty good idea of things to do I left it simmering for a few more days before diving into code.

I found an implementation of the Graph, Node and Edge models on Github and used those as a starting point.

Graph refers to the network, Node refers to a numbered cycling node and Edge refers to the trajectory between 2 cycling nodes. The trajectory distance is the weight of the Edge. And that’s all you need.

When 2 non-connected nodes are tapped the algorithm calculates the shortest distance and returns a GraphRoute, which contains an array of GraphRouteSteps. These can be translated back to network nodes and trajectories and voila: there’s your shortest route.

Result

The app can now calculate the shortest route from a node near the coast to a node near Germany in less than 2 seconds … a route that spans more than 315km. It’s a big step forward compared to error messages saying that 2 nodes are too far apart.

At some point in time the app will support route calculation between 2 place names instead of just tapping annotations on the map. I’ve had quite a few support mails where people asked for this.

More on that in a future blog post.