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

Vicky Vergara vicky_vergara at hotmail.com
Wed Aug 26 16:52:41 PDT 2015

Hello Christopher,
   We have several issues going with pgr_apspWarshall that you might want to check out in gitgub:

   The acronym apsp, is not well suited as it does not return shortest paths (I can read that you already noticed that)

    But lets suppose for the benefit of our minds that a :
        pgr_floydWarshall returns the matrix table
    So pgr_apspWarshall would be in charge doing what the name suggests. (all of the paths, of for some particular pair?)

    I don't know the availability of the original developer, but,
    We are be very interested in looking at your implementation for the would be pgr_apspWarshall. 

    Right now we are in a middle of releasing 2.1, and only bugs of pgr_dijkstra, pgr_ksp and pgr_drivingDistance are being taken care of at this moment. But once we we make a the we can start looking at other functions.


From: lr at pcorp.us
To: postgis-users at lists.osgeo.org
Date: Wed, 26 Aug 2015 17:46:32 -0400
CC: pgrouting-dev at lists.osgeo.org; pgrouting-users at lists.osgeo.org
Subject: Re: [pgrouting-users] [postgis-users] floyd-warhall all pairs	shortest path

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
Pgrouting-users mailing list
Pgrouting-users at lists.osgeo.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20150826/4eddba32/attachment.html>

More information about the Pgrouting-users mailing list