How to compute single source shortest paths with OSRM?

Question

I've been playing around with the OSRM routing library recently. It seems to be highly efficient at solving the shortest path problem. However, I didn't see how to compute single source shortest paths with it. More precisely, given a fixed starting point, compute the shortest distances to all locations that can be reached within a given distance limit (e.g., reachable within 30 minutes).

OSRM uses contraction hierarchies internally. From my understanding, this technique is way superior to Dijkstra's algorithm when it comes to computing the distance between two locations in real world data. However, for my problem, Dijkstra's algorithm seems to fit better, doesn't it?

Does OSRM provide an API to compute single source shortest path problems (with a limit on the distance)? Are there other free routing libraries that are better suited for this type of problem? Preferably one with good support for OpenStreetMap data.

Gapes

Answer 1

OSRM is using contraction hierarchies (CH) to be that fast for "one to one routing". To make CH working you need an adapted bidirectional algorithm (A*, Dijkstra, ...) so the single source case is more difficult. BUT a one to many algorithm is relative simple if you know up front which destinations you want.

Also have a look into the paper "Fast Detour Computation for Ride Sharing" or here if you want a solution for a "non goal-directed, bidirectional search" which uses lookup tables.

other free routing libraries?

I would suggest my Java GraphHopper project ;)

but there are of course more: http://wiki.openstreetmap.org/wiki/Routing

Sami