<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="gmail_extra">This adaption requires the pgrouting source code to be changed. (the two lines marked with a * need to be added)</div><div class="gmail_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="gmail_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="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_extra">function neighbors_list(links[])</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>neighbors[][] := [][] // associative list containing lists of all neighbors for each node</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>for link in links[]</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>add link[node2] to neigbors[link[node1]]</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>add link[node1] to neigbors[link[node2]]</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>return neighbors[][]</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span></div><div class="gmail_extra">function P_from_D(D[][], links[])</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>neighbors[][] := neighbors_list(links[])</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>P[][] := sizeof(D[][])</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>for i from 1 to |V|</div><div class="gmail_extra"> for j from 1 to |V|</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>min_dist := inf</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>next := null</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>for neighbor in neighbors[i] </div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>dist := D[i][neighbor] + D[neighbor][j]</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>if dist < min_dist</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>min_dist := dist</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>next := neighbor</div><div class="gmail_extra"><span class="" style="white-space:pre"> </span>P[i][j] := next</div></div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">best regards, Christoph</div><div class="gmail_extra"><br><div class="gmail_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="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><u></u> <u></u></p><div><p class="MsoNormal" style="margin-bottom:12pt"><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="MsoNormal" align="center" style="text-align:center"><span style="font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></span></div><p class="MsoNormal" style="margin-bottom:12pt"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p><div><div><p class="MsoNormal"><span style="font-family:Calibri,sans-serif">Hi,<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif">I found that the Floyd–Warshall algorithm works well for my purpose. <u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><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="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:Calibri,sans-serif">Does pgr_apspWarshall support this?<u></u><u></u></span></p></div><div><p class="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><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="MsoNormal"><span style="font-family:Calibri,sans-serif"> <u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:Calibri,sans-serif">best regards, Christoph Mayrhofer<u></u><u></u></span></p></div></div></div></div></div><p class="MsoNormal"><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>