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

Fri Aug 28 05:29:31 PDT 2015

Hi Vicky,

I had a look at the implementation on github. Unfortunately I am not very
deep into C.
However, I put the pseudocode of the algorithm below with the two necessary
extra lines that allow us to later reconstruct the path with the function
Path() below.

*let* dist be a |V| × |V| array of minimum distances initialized to ∞
(infinity)*let* next be a |V| × |V| array of vertex indices
initialized to *null*
*procedure* *FloydWarshallWithPathReconstruction* ()
   *for each* edge (u,v)
      dist[u][v] ← w(u,v)  *// the weight of the edge (u,v)*
*     next[u][v] ← v   // << -- this line is needed to reconstruct the
path later
   *for* k *from* 1 *to* |V| *// standard Floyd-Warshall implementation*
      *for* i *from* 1 *to* |V|
         *for* j *from* 1 *to* |V|
            *if* dist[i][k] + dist[k][j] < dist[i][j] *then*
               dist[i][j] ← dist[i][k] + dist[k][j]
*              next[i][j] ← next[i][k]   // << -- this line is needed
to reconstruct the path later

// this function reconstructs the path from the "next"
matrix*procedure* Path(u, v)
   *if* next[u][v] = null *then*
       *return* []
   path = [u]
   *while u ≠ v*
       u ← next[u][v]
       path.append(u)
   *return* path

This adaption requires the pgrouting source code to be changed. (the two
lines marked with a * need to be added)
Since I already mentioned that I am not very much into that I came up with
the following algorithm that allows to reconstruct the path from the
resulting distance matrix as produced by the current pgr_apspWarshall
It does not require the matrix with the first node of the path (next[][])
as mentioned in the code snippet above, but uses the distance matrix in
combination with the link list to build the path.
So what I currently do: use pgrouting to get the distance matrix ... and
then use the following algorithm to get the paths from that:

function neighbors_list(links[])
neighbors[][] := [][] // associative list containing lists of all neighbors
for each node
for link in links[]
add link[node2] to neigbors[link[node1]]
add link[node1] to neigbors[link[node2]]
return neighbors[][]
function P_from_D(D[][], links[])
neighbors[][] := neighbors_list(links[])
P[][] := sizeof(D[][])
for i from 1 to |V|
               for j from 1 to |V|
min_dist := inf
next := null
for neighbor in neighbors[i]
dist := D[i][neighbor] + D[neighbor][j]
if dist < min_dist
min_dist := dist
next := neighbor
P[i][j] := next

best regards, Christoph

On Thu, Aug 27, 2015 at 5:27 AM, Paragon Corporation <lr at pcorp.us> wrote:

> Just in case you aren't subscribed to pgRouting mailing list yet. Vicky
> answered some of your questions on the list.
>
>
>
> *From:* pgrouting-users-bounces at lists.osgeo.org [mailto:
> pgrouting-users-bounces at lists.osgeo.org] *On Behalf Of *Vicky Vergara
> *Sent:* Wednesday, August 26, 2015 7:53 PM
> *To:* pgRouting users mailing list <pgrouting-users at lists.osgeo.org>;
> pgrouting-dev at lists.osgeo.org
> *Subject:* Re: [pgrouting-users] [postgis-users] floyd-warhall all pairs
> shortest path
>
>
>
> Hello Christopher,
>
>    We have several issues going with pgr_apspWarshall that you might want
> to check out in gitgub:
> https://github.com/pgRouting/pgrouting
>
>    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.
>
>  Vicky
>
> ------------------------------
>
> 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
> <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
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20150828/6c0c6bcc/attachment.html>