Dijkstra traverses each node of the graph and returns to the specified start node to determine (calculate) the shortest path based on the cost. <br><br>For driving-distance, the Dijkstra algorithm was modified so that it does not have to return back, and instead just accumulate the cost of each node from the start node while traversing the graph.<br>
<br>Mario.<br><br><div class="gmail_quote">On Wed, Mar 7, 2012 at 10:19 AM, Steve Horn <span dir="ltr"><steve@stevehorn.cc></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
First of all, thanks for your contribution! I am using it successfully and am getting great results.<div><br></div><div>Can you expound a little more on "uses a slightly modified Dijkstra"? I'm trying to imagine how you start from the starting vertex and "crawl" out to all the surrounding vertexes. </div>
<div><br></div><div><div><div class="h5"><br><div class="gmail_quote">On Tue, Mar 6, 2012 at 9:00 PM, Mario Basa <span dir="ltr"><<a href="mailto:mario.basa@gmail.com" target="_blank">mario.basa@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>Hello Steve,<br><br>I wrote the initial code for the driving_distance, although Anton modified it quite a bit afterwards.<br><br>Basically it uses a slightly modified Dijkstra that traverses the graph from a starting point while measuring the lenght/time along the way. After a set length/time has been reached, *all* the nodes (along with the x,y coordinates) are passed to CGAL to get the outer points and create a concave hull polygon.<br>
<br>The bottleneck here is in the passing of the nodes since in a dense graph, the data can be quite large. Anton and I were trying all sorts of ways to filter first the nodes, but couldn't find an efficient method without loosing accuracy.<br>
<br>Regards,<br><br>Mario.<br><br><br><div class="gmail_quote"><div><div>On Wed, Mar 7, 2012 at 9:36 AM, Steve Horn <span dir="ltr"><steve@stevehorn.cc></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div>
Hello list.
<div><br></div><div>I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (<a href="http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html" target="_blank">http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html</a>).</div>
<div><br></div><div>Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn't mind giving a synopsis of the overall approach that the algorithm takes?</div>
<div><br></div><div>Thanks!</div>
<br></div></div>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br>
<br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div></div></div><div class="im">-- <br>Steve Horn<br><a href="http://www.stevehorn.cc" target="_blank">http://www.stevehorn.cc</a><br>steve@stevehorn.cc<br><a href="http://twitter.com/stevehorn" target="_blank">http://twitter.com/stevehorn</a><br>
<a href="tel:740-503-2300" value="+17405032300" target="_blank">740-503-2300</a><br><br>
</div></div>
<br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br>