<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'>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> <br><br><div><hr id="stopSpelling">From: lr@pcorp.us<br>To: postgis-users@lists.osgeo.org<br>Date: Wed, 26 Aug 2015 17:46:32 -0400<br>CC: pgrouting-dev@lists.osgeo.org; pgrouting-users@lists.osgeo.org<br>Subject: Re: [pgrouting-users] [postgis-users] floyd-warhall all pairs shortest path<br><br><style><!--
.ExternalClass p.ecxMsoNormal, .ExternalClass li.ecxMsoNormal, .ExternalClass div.ecxMsoNormal {
font-size:12.0pt;
font-family:"Times New Roman",serif;
}
.ExternalClass a:link, .ExternalClass span.ecxMsoHyperlink {
color:blue;
text-decoration:underline;
}
.ExternalClass span.ecxMsoHyperlinkFollowed {
color:purple;
text-decoration:underline;
}
.ExternalClass span.ecxEmailStyle17 {
font-family:"Calibri",sans-serif;
color:#1F497D;
}
.ExternalClass .ecxMsoChpDefault {
font-family:"Calibri",sans-serif;
}
.ExternalClass div.ecxWordSection1 {
}
--></style><div class="ecxWordSection1"><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;">Christopher,</span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;"> </span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;">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</span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;"> </span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;">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></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;"> </span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;">Hope that helps,</span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;">Regina</span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;"> </span></p><p class="ecxMsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;"> </span></p><p class="ecxMsoNormal" style=""><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;"> postgis-users-bounces@lists.osgeo.org [mailto:postgis-users-bounces@lists.osgeo.org] <b>On Behalf Of </b>Christoph Mayrhofer<br><b>Sent:</b> Monday, August 24, 2015 12:09 PM<br><b>To:</b> postgis-users@lists.osgeo.org<br><b>Subject:</b> [postgis-users] floyd-warhall all pairs shortest path</span></p><p class="ecxMsoNormal" style=""> </p><div><div><p class="ecxMsoNormal" style="">Hi,</p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">I looked into all pairs shortest path routing algorithms to use for traffic simulations. </p></div><div><p class="ecxMsoNormal" style="">I found that the Floyd–Warshall algorithm works well for my purpose. </p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">pgRouting has a function for this which produces a table with the shortest path distance between all source/destination pairs.</p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">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></p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">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. </p></div><div><p class="ecxMsoNormal" style="">This information is sufficient to reconstruct all paths using the parent child relationship recursively.</p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">Does pgr_apspWarshall support this?</p></div><div><p class="ecxMsoNormal" style="">Or can anyone point to the person that implemented pgr_apspWarshall?</p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">So far I use my own implementation outside of PostGIS, but I think whis functionality might be of interest for others too.</p></div><div><p class="ecxMsoNormal" style=""> </p></div><div><p class="ecxMsoNormal" style="">best regards, Christoph Mayrhofer</p></div></div></div><br>_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users</div> </div></body>
</html>