[pgrouting-dev] FW: [pgrouting-users] [postgis-users] floyd-warhall all pairs shortest path
Vicky Vergara
vicky_vergara at hotmail.com
Fri Aug 28 05:44:31 PDT 2015
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 at stud.sbg.ac.at
To: pgrouting-dev at 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 pathThis 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 pathChristopher, 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 http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20150828/883c392e/attachment-0001.html>
More information about the pgrouting-dev
mailing list