<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'><span style="font-family:Calibri,sans-serif;">Christopher</span>,<br>I added your pseudocode into this issue<br><a href="https://github.com/pgRouting/pgrouting/issues/324" target="_blank">https://github.com/pgRouting/pgrouting/issues/324</a><br><br>Thanks.<br>Vicky<br><br><div><hr id="stopSpelling">Date: Fri, 28 Aug 2015 14:29:31 +0200<br>From: mayrhoferchr@stud.sbg.ac.at<br>To: pgrouting-dev@lists.osgeo.org<br>Subject: Re: [pgrouting-dev] FW: [pgrouting-users] [postgis-users] floyd-warhall all pairs shortest path<br><br><div dir="ltr">Hi Vicky,<div><br></div><div>I had a look at the implementation on github. Unfortunately I am not very deep into C.</div><div>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.</div><div><pre style="font-family:monospace,Courier;color:black;border:1px solid rgb(221,221,221);padding:1em;white-space:pre-wrap;line-height:1.3em;font-size:14px;background-color:rgb(249,249,249);"><b>let</b> dist be a |V| ¡Ñ |V| array of minimum distances initialized to ¡Û (infinity)
<b>let</b> next be a |V| ¡Ñ |V| array of vertex indices initialized to <b>null</b>
<b>procedure</b> <i>FloydWarshallWithPathReconstruction</i> ()
<b>for each</b> edge (u,v)
dist[u][v] ¡ö w(u,v) <i>// the weight of the edge (u,v)</i>
* next[u][v] ¡ö v // << -- this line is needed to reconstruct the path later
<b>for</b> k <b>from</b> 1 <b>to</b> |V| <i>// standard Floyd-Warshall implementation</i>
<b>for</b> i <b>from</b> 1 <b>to</b> |V|
<b>for</b> j <b>from</b> 1 <b>to</b> |V|
<b>if</b> dist[i][k] + dist[k][j] < dist[i][j] <b>then</b>
dist[i][j] ¡ö dist[i][k] + dist[k][j]
* next[i][j] ¡ö next[i][k] <span style="font-size:14px;line-height:1.3em;">// << -- this line is needed to reconstruct the path later</span><br>
<br></pre><pre style="font-family:monospace,Courier;color:black;border:1px solid rgb(221,221,221);padding:1em;white-space:pre-wrap;line-height:1.3em;font-size:14px;background-color:rgb(249,249,249);">// this function reconstructs the path from the "next" matrix
<b>procedure</b> Path(u, v)
<b>if</b> next[u][v] = null <b>then</b>
<b>return</b> []
path = [u]
<b>while u ¡Ú v</b>
u ¡ö next[u][v]
path.append(u)
<b>return</b> path</pre></div><div class="ecxgmail_extra">This adaption requires the pgrouting source code to be changed. (the two lines marked with a * need to be added)</div><div class="ecxgmail_extra">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 <span style="font-family:Calibri,sans-serif;">pgr_apspWarshall</span><br>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. </div><div class="ecxgmail_extra">So what I currently do: use pgrouting to get the distance matrix ... and then use the following algorithm to get the paths from that:</div><div class="ecxgmail_extra"><br></div><div class="ecxgmail_extra"><div class="ecxgmail_extra">function neighbors_list(links[])</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>neighbors[][] := [][] // associative list containing lists of all neighbors for each node</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>for link in links[]</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>add link[node2] to neigbors[link[node1]]</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>add link[node1] to neigbors[link[node2]]</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>return neighbors[][]</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span></div><div class="ecxgmail_extra">function P_from_D(D[][], links[])</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>neighbors[][] := neighbors_list(links[])</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>P[][] := sizeof(D[][])</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>for i from 1 to |V|</div><div class="ecxgmail_extra"> for j from 1 to |V|</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>min_dist := inf</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>next := null</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>for neighbor in neighbors[i] </div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>dist := D[i][neighbor] + D[neighbor][j]</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>if dist < min_dist</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>min_dist := dist</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>next := neighbor</div><div class="ecxgmail_extra"><span style="white-space:pre;"> </span>P[i][j] := next</div></div><div class="ecxgmail_extra"><br></div><div class="ecxgmail_extra"><br></div><div class="ecxgmail_extra">best regards, Christoph</div><div class="ecxgmail_extra"><br><div class="ecxgmail_quote">On Thu, Aug 27, 2015 at 5:27 AM, Paragon Corporation <span dir="ltr"><<a href="mailto:lr@pcorp.us" target="_blank">lr@pcorp.us</a>></span> wrote:<br><blockquote class="ecxgmail_quote" style="border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex;"><div lang="EN-US"><div><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);">Just in case you aren't subscribed to pgRouting mailing list yet. Vicky answered some of your questions on the list.<u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);"><u></u> <u></u></span></p><div><div style="border-style:solid none none;border-top-color:rgb(225,225,225);border-top-width:1pt;padding:3pt 0in 0in;"><p class="ecxMsoNormal"><b><span style="font-size:11pt;font-family:Calibri,sans-serif;">From:</span></b><span style="font-size:11pt;font-family:Calibri,sans-serif;"> <a href="mailto:pgrouting-users-bounces@lists.osgeo.org" target="_blank">pgrouting-users-bounces@lists.osgeo.org</a> [mailto:<a href="mailto:pgrouting-users-bounces@lists.osgeo.org" target="_blank">pgrouting-users-bounces@lists.osgeo.org</a>] <b>On Behalf Of </b>Vicky Vergara<br><b>Sent:</b> Wednesday, August 26, 2015 7:53 PM<br><b>To:</b> pgRouting users mailing list <<a href="mailto:pgrouting-users@lists.osgeo.org" target="_blank">pgrouting-users@lists.osgeo.org</a>>; <a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br><b>Subject:</b> Re: [pgrouting-users] [postgis-users] floyd-warhall all pairs shortest path<u></u><u></u></span></p></div></div><p class="ecxMsoNormal"><u></u> <u></u></p><div><p class="ecxMsoNormal" style=""><span style="font-family:Calibri,sans-serif;">Hello Christopher,<br> <br> We have several issues going with pgr_apspWarshall that you might want to check out in gitgub:<br><a href="https://github.com/pgRouting/pgrouting" target="_blank">https://github.com/pgRouting/pgrouting</a> <br><br> The acronym apsp, is not well suited as it does not return shortest paths (I can read that you already noticed that)<br><br> But lets suppose for the benefit of our minds that a :<br> pgr_floydWarshall returns the matrix table<br> So pgr_apspWarshall would be in charge doing what the name suggests. (all of the paths, of for some particular pair?)<br><br> I don't know the availability of the original developer, but,<br> We are be very interested in looking at your implementation for the would be pgr_apspWarshall. <br><br> 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.<br><br> Vicky<br> <u></u><u></u></span></p><div><div class="ecxMsoNormal" style="text-align:center;" align="center"><span style="font-family:Calibri,sans-serif;"><hr align="center" size="2" width="100%"></span></div><p class="ecxMsoNormal" style=""><span style="font-family:Calibri,sans-serif;">From: <a href="mailto:lr@pcorp.us" target="_blank">lr@pcorp.us</a><br>To: <a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>Date: Wed, 26 Aug 2015 17:46:32 -0400<br>CC: <a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>; <a href="mailto:pgrouting-users@lists.osgeo.org" target="_blank">pgrouting-users@lists.osgeo.org</a><br>Subject: Re: [pgrouting-users] [postgis-users] floyd-warhall all pairs shortest path<u></u><u></u></span></p><div><div class="h5"><div><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);">Christopher,</span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);"> </span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);">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: <a href="http://pgrouting.org/support.html" target="_blank">http://pgrouting.org/support.html</a></span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);"> </span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);">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.</span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);"> </span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);">Hope that helps,</span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);">Regina</span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);"> </span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125);"> </span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><b><span style="font-size:11pt;font-family:Calibri,sans-serif;">From:</span></b><span style="font-size:11pt;font-family:Calibri,sans-serif;"> <a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@lists.osgeo.org</a> [<a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">mailto:postgis-users-bounces@lists.osgeo.org</a>] <b>On Behalf Of </b>Christoph Mayrhofer<br><b>Sent:</b> Monday, August 24, 2015 12:09 PM<br><b>To:</b> <a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br><b>Subject:</b> [postgis-users] floyd-warhall all pairs shortest path</span><span style="font-family:Calibri,sans-serif;"><u></u><u></u></span></p><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p><div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">Hi,<u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">I looked into all pairs shortest path routing algorithms to use for traffic simulations. <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">I found that the Floyd¡VWarshall algorithm works well for my purpose. <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">pgRouting has a function for this which produces a table with the shortest path distance between all source/destination pairs.<u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">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 <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" target="_blank">https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a><u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">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. <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">This information is sufficient to reconstruct all paths using the parent child relationship recursively.<u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">Does pgr_apspWarshall support this?<u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">Or can anyone point to the person that implemented pgr_apspWarshall?<u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">So far I use my own implementation outside of PostGIS, but I think whis functionality might be of interest for others too.<u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"> <u></u><u></u></span></p></div><div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;">best regards, Christoph Mayrhofer<u></u><u></u></span></p></div></div></div></div></div><p class="ecxMsoNormal"><span style="font-family:Calibri,sans-serif;"><br>_______________________________________________ Pgrouting-users mailing list <a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.org</a> <a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><u></u><u></u></span></p></div></div></div></div></blockquote></div><br></div></div>
<br>_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</div> </div></body>
</html>