[postgis-users] floyd-warhall all pairs shortest path

[Christoph Mayrhofer]

Hi,

I looked into all pairs shortest path routing algorithms to use for traffic simulations. 

I found that the Floyd–Warshall algorithm works well for my purpose. 

pgRouting has a function for this which produces a table with the shortest path distance between all source/destination pairs.

In order to get the actual paths rather than only distances it suffices to make a minor adaption to the algorithm as described in the path reconstruction section in https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

It is basically supposed to output the first node of the shortest path between the source and destination in addition to the overall distance of that route. 

This information is sufficient to reconstruct all paths using the parent child relationship recursively.

Does pgr_apspWarshall support this?

Or can anyone point to the person that implemented pgr_apspWarshall?

So far I use my own implementation outside of PostGIS, but I think whis functionality might be of interest for others too.

best regards, Christoph Mayrhofer

[Paragon Corporation]

Christopher,

 

This is the wrong group to be asking this question.  You want to be on the pgRouting Users or pgRouting develop group.  Join details here: http://pgrouting.org/support.html

 

This question probably makes sense to ask on both pgRouting users and dev, since it is both a development change and a "Would user's like this and a support question?"  So I've cc'd both.

 

Hope that helps,

Regina