Calculate shortest path and distance between multiple OD pairs using pgr_dijkstra one-to-one

Question

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.

Answer 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.