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

Paragon Corporation lr at pcorp.us
Wed Aug 26 14:46:32 PDT 2015



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,




From: postgis-users-bounces at lists.osgeo.org [mailto:postgis-users-bounces at lists.osgeo.org] On Behalf Of Christoph Mayrhofer
Sent: Monday, August 24, 2015 12:09 PM
To: postgis-users at lists.osgeo.org
Subject: [postgis-users] floyd-warhall all pairs shortest path




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/pgrouting-users/attachments/20150826/d07e1f50/attachment.html>

More information about the Pgrouting-users mailing list