The QGIS Road Graph plugin

QGIS offers a plugin that will solve a shortest path problem across any vector polyline layer in any format - the Road Graph plugin.

The advantage of using this plugin over pgRouting is that you don't need to do anything special to your polyline layer to route across it. As long as your polyline segments are all connected you can use it. In my example I am using an extract of Ordnance Survey's ITN layer for the UK.

Once the plugin is enabled you need to adjust the settings available under Vector > Road Graph > Settings.

This allows you to set the time and distance units. The topology tolerance I leave set to 0 - I know the ITN network is good. Choose your network layers from the drop down (it needs to be loaded in the project). My ITN layer has been updated with backwards, forwards and two-way attributes and I have a speed field in km/h so I have used those. Once you have filled in all the settings click OK to close the dialogue box.

The shortest path solver allows you to select a start and end point using the coordinate capture buttons (or you can type your coordinates in manually). Select the path cost to evaluate - length or time - using the drop down menu. Click calculate to generate your result. This takes some time depending on the size of your network.

Performance

My ITN extract has 80,000 records (Tayside extent, PostGIS table) and takes between 8 and 10 seconds to return a result. Running the same query but using OS Open Roads for the whole UK (3.18 million links, PostGIS table) returns a Bad allocation error. A small local extract of OS Open Roads with 300 links returns a result instantly. Using the OS Strategi network (full UK, 245,000 links, PostGIS table) returns a route in 20 - 25 seconds.

Using a 100km tile of the OS Digital River Network with 127,000 links as my "road" network returned results in 17 - 20 seconds.

Caveats

The plugin has some limitations especially if you want detailed results returned. In the image below the route is going from left to right. You'll notice that because I have set direction attributes the solution correctly routes around the roundabout. Where it fails is where it jumps from the underpass onto the dual carriageway above to get to McDonalds using the quickest path.

Using the shortest path with the same start and end coordinates highlights the lack of grade separation support in the plugin.

However, that said, for general use the road graph plugin returns good approximations of the true shortest path between two places in the real world. Set the direction and speed fields up correctly (if your network has them) and it goes some way to improving results.