2

My goal is to find the distance and shortest path between 1000+ Origin-Destination pairs in a road network. I have a table with the pair ID, the origin vertex ID and the destination vertex ID for each pair. Everything works fine when I use the pgr_dijkstra, where I get a path and a agg_cost for the following example:

SELECT * FROM pgr_dijkstra(
'SELECT gid as id, source, target, length as cost FROM route1',
48302, 44382, FALSE); 

What I would like to do is replace the origin and destination vertices (48302, 44382) by the Origin and Destination vertex id columns from my table, matched by the pair ID. In other words, I'd like to get the distance and path for all my OD pairs in a single query.

1 Answer 1

1

do you mean finding the shortest route from all points to all other points on your network?

That's possible with the All Pairs Shortest Path, Floyd-Warshall Algorithm but in "big O" notation it's O(n^3) so it will take a LONG time (10 nodes will take 1,000 units of time, 100 nodes will take 1,000,000 units of time...)

You may also run out of memory for more than a few thousand points.

There's also an implementation of Johnson’s Algorithm which I haven't tried, which might be faster.

EDIT re-reading your question, that's probably overkill if you just want the path/distance for a subset of the nodes in your network.

1
  • 1
    Here is what I wanted: I have a daily commute for 1000+ people (Origin and destination) and I wanted to measure the distance and path for each individual. I didn't wanted the distance from all-to-all origin-destination points. I think I managed to find a way,with which I will update my post if it ends up working.
    – Félix Lam
    May 12, 2017 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.