[prev in list] [next in list] [prev in thread] [next in thread]
List: postgis-users
Subject: Re: [postgis-users] floyd-warhall all pairs shortest path
From: "Paragon Corporation" <lr () pcorp ! us>
Date: 2015-08-26 21:46:32
Message-ID: 000f01d0e048$ac9e3160$05da9420$ () pcorp ! us
[Download RAW message or body]
This is a multipart message in MIME format.
[Attachment #2 (multipart/alternative)]
This is a multipart message in MIME format.
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
[Attachment #5 (text/html)]
<html xmlns:v="urn:schemas-microsoft-com:vml" \
xmlns:o="urn:schemas-microsoft-com:office:office" \
xmlns:w="urn:schemas-microsoft-com:office:word" \
xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" \
xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type \
content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 \
(filtered medium)"><style><!-- /* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div \
class=WordSection1><p class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Christopher,<o:p></o:p></span></p><p \
class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p \
class=MsoNormal><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<o:p></o:p></span></p><p class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p \
class=MsoNormal><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.<o:p></o:p></span></p><p class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p \
class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Hope that \
helps,<o:p></o:p></span></p><p class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Regina<o:p></o:p></span></p><p \
class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p \
class=MsoNormal><span \
style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p \
class=MsoNormal style='margin-left:.5in'><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<o:p></o:p></span></p><p class=MsoNormal \
style='margin-left:.5in'><o:p> </o:p></p><div><div><p class=MsoNormal \
style='margin-left:.5in'>Hi,<o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'><o:p> </o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>I looked into all pairs shortest path routing algorithms to \
use for traffic simulations. <o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>I found that the Floyd–Warshall algorithm works well for \
my purpose. <o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'><o:p> </o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>pgRouting has a function for this which produces a table \
with the shortest path distance between all source/destination \
pairs.<o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'><o:p> </o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>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">https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a><o:p></o:p></p></div><div><p \
class=MsoNormal style='margin-left:.5in'><o:p> </o:p></p></div><div><p \
class=MsoNormal style='margin-left:.5in'>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. <o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>This information is sufficient to reconstruct all paths \
using the parent child relationship recursively.<o:p></o:p></p></div><div><p \
class=MsoNormal style='margin-left:.5in'><o:p> </o:p></p></div><div><p \
class=MsoNormal style='margin-left:.5in'>Does pgr_apspWarshall support \
this?<o:p></o:p></p></div><div><p class=MsoNormal style='margin-left:.5in'>Or can \
anyone point to the person that \
implemented pgr_apspWarshall?<o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'><o:p> </o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>So far I use my own implementation outside of PostGIS, but I \
think whis functionality might be of interest for others \
too.<o:p></o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'><o:p> </o:p></p></div><div><p class=MsoNormal \
style='margin-left:.5in'>best regards, Christoph \
Mayrhofer<o:p></o:p></p></div></div></div></body></html>
_______________________________________________
postgis-users mailing list
postgis-users@lists.osgeo.org
http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic