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