[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20150824/8c0f9dac/attachment.html>