[pgrouting-users] Large OD matrices

Stephen Woodbridge woodbri at swoodbridge.com
Tue Dec 23 07:15:18 PST 2014

On 12/23/2014 3:55 AM, Hans Skov-Petersen wrote:
> Hi List,
> Being rather new at PgRouting (but not to network analysis in general),
> I am looking for means by which I efficiently can construct all pair,
> shortest path OD matrices for quite large networks (i.e. a graph of the
> road network of Denmark, 2.107.981 edges, 860.380 nodes).

I'm not familiar with the term OD, but I assume you mean Distance 
matrices of some kind.

> I am looking at the All Pairs Shortest Path, Johnson’s or Floyd-Warshall
> Algorithms.

If you are generating a distance matrix for 860,380 nodes that will be 
740,253,744,400 cells which is really HUGE amount of data!

What are you planning on doing with all this data?

> Questions:
> 1)Can anyone guide me to examples of the SQL syntax (or other code)
> involved in applying the algorithms

As Manikanta mentioned look at the tutorial, you can also look at the 
test files for trivial examples:



> 2)Is there a way that the search (and output) can be simplified by
> limiting the search to only take OD within a given max-search-radius
> into account?

select seq, id1, id2, round(cost::numeric, 2) as cost from 
pgr_apspWarshall('select id, source, target, cost from apspw', false, 

The first argument to the function is a sql query for the edges that you 
want to be used to build your graph from. So you can restriction what 
edges you pass it by change that query to something like:

'select id, source, target, cost from apspw where st_dwithin(geom, 
st_setsrid(st_makepoint(<longitude>,<latitude>),4326), <radius>)'

Where <radius> is in degrees and 1 degrees is approximately equal to 
127788 meters.


> Cheers and Thanks
> Hans
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

More information about the Pgrouting-users mailing list