Christopher,
I added your pseudocode into this issue
https://github.com/pgRouting/pgrouting/issues/324
Thanks.
Vicky
Date: Fri, 28 Aug 2015 14:29:31 +0200
From: mayrhoferchr@stud.sbg.ac.at
To: pgrouting-dev@lists.osgeo.org
Subject: Re: [pgrouting-dev] FW: [pgrouting-users] [postgis-users] floyd-warhall all pairs shortest path
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@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@lists.osgeo.org [mailto:pgrouting-users-bounces@lists.osgeo.org] On Behalf Of Vicky Vergara
Sent: Wednesday, August 26, 2015 7:53 PM
To: pgRouting users mailing list <pgrouting-users@lists.osgeo.org>; pgrouting-dev@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@pcorp.us
To: postgis-users@lists.osgeo.org
Date: Wed, 26 Aug 2015 17:46:32 -0400
CC: pgrouting-dev@lists.osgeo.org; pgrouting-users@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@lists.osgeo.org [mailto:postgis-users-bounces@lists.osgeo.org] On Behalf Of Christoph Mayrhofer
Sent: Monday, August 24, 2015 12:09 PM
To: postgis-users@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@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________ pgrouting-dev mailing list pgrouting-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/pgrouting-dev