[pgrouting-dev] driving_distance Synopsis

[Stephen Woodbridge]

On 3/6/2012 11:11 PM, Mario Basa wrote:
> Dijkstra traverses each node of the graph and returns to the specified
> start node to determine (calculate) the shortest path based on the cost.
>
> 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.
>
> Mario.
>
> On Wed, Mar 7, 2012 at 10:19 AM, Steve Horn <steve at stevehorn.cc> wrote:
>
>     First of all, thanks for your contribution! I am using it
>     successfully and am getting great results.
>
>     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.

Steve,

Dijkstra does not crawl out to each node, it instead converts the graph 
into a tree with the start node as the root of the tree. So from the 
root node you can travel only to the connected nodes down the tree, and 
from each of those nodes only down to the connected nodes again. Once a 
node has been added to the tree it is marked in the graph so you can 
node add it again unless it is a smaller cost, then you have to fixup 
the tree. And so on and so on. The algorithms in graph theory are 
designed for the most part to convert complex problems of analyzing 
graphs into simpler problems that are easier to solve. In the case of 
Dijkstra, the resulting tree represents the possible paths that one 
could "crawl". If you sum the cost of each edge in the tree to a leaf 
node that is the cost to get there.

The slightly modified Dijkstra keeps that summed cost as the tree is 
developed, so you do not have to do the summing at the end.

-Steve

>     On Tue, Mar 6, 2012 at 9:00 PM, Mario Basa <mario.basa at gmail.com
>     <mailto:mario.basa at gmail.com>> wrote:
>
>
>         Hello Steve,
>
>         I wrote the initial code for the driving_distance, although
>         Anton modified it quite a bit afterwards.
>
>         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.
>
>         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.
>
>         Regards,
>
>         Mario.
>
>
>         On Wed, Mar 7, 2012 at 9:36 AM, Steve Horn <steve at stevehorn.cc>
>         wrote:
>
>             Hello list.
>
>             I am interested in digging in more to the driving_distance
>             functions to do some refining and perhaps improve the
>             usefulness of the results
>             (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
>
>             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?
>
>             Thanks!
>
>             _______________________________________________
>             pgrouting-dev mailing list
>             pgrouting-dev at lists.osgeo.org
>             <mailto:pgrouting-dev at lists.osgeo.org>
>             http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>         _______________________________________________
>         pgrouting-dev mailing list
>         pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>         http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
>     --
>     Steve Horn
>     http://www.stevehorn.cc
>     steve at stevehorn.cc
>     http://twitter.com/stevehorn
>     740-503-2300 <tel:740-503-2300>
>
>
>     _______________________________________________
>     pgrouting-dev mailing list
>     pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>     http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev