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

[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

 

 

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

 

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