<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 7/6/2012 6:52 PM, Stephen Woodbridge
wrote:<br>
</div>
<blockquote cite="mid:4FF717D9.8040401@swoodbridge.com" type="cite">On
7/6/2012 10:00 AM, Sylvain Housseman wrote:
<br>
<blockquote type="cite">Dear pg_routers,
<br>
<br>
I added a page describing my first (very minor) contribution to
the wiki:
<br>
<a class="moz-txt-link-freetext" href="https://github.com/pgRouting/pgrouting/wiki/One_to_many-Dijkstra---To-review">https://github.com/pgRouting/pgrouting/wiki/One_to_many-Dijkstra---To-review</a>
<br>
<br>
<br>
I don't know how to make it accessible (and at first if the
function
<br>
really is relevant, I believe that many of you coded a similar
<br>
function...).
<br>
As soon as it does not really modify the method
(boost_dijkstra), I
<br>
think the Algorithms section is not appropriate.
<br>
<br>
Should I
<br>
- remove the whole stuff?
<br>
- add a new section to
<a class="moz-txt-link-freetext" href="https://github.com/pgRouting/pgrouting/wiki">https://github.com/pgRouting/pgrouting/wiki</a> (i.e.
<br>
"Optional wrappers" or "Contrib. / betas")?
<br>
<br>
Please feedback if you have the time to try it;
<br>
</blockquote>
<br>
Hi Sylvain,
<br>
<br>
Thank you for your contribution. It is very much appreciated.
<br>
<br>
I have a question, if I have 10 destination nodes, how many times
to you solve the graph after it is built?
<br>
</blockquote>
Only once...<br>
<blockquote cite="mid:4FF717D9.8040401@swoodbridge.com" type="cite">
<br>
The Dijkstra algorithm converts a graph into a tree. If you search
the tree for the destination nodes, you should be able to extract
the path as the reverse of the nodes from the destination up to
the root (aka: the source node). So for a single solution, can can
extract any of the path from any destination node in the tree.
<br>
<br>
Is this how your algorithm works?
<br>
</blockquote>
I wouldn't have explained it better!<br>
<br>
To detail the code modifications, I just replaced "vertex_descriptor
_target;" by an array of the same type, initialized as "_target[i] =
vertex(end_vertices[i], graph);"<br>
and after the resolution, I loop on nb_targets to build the paths as
<i>rewinding</i> on the tree (_target[i] =
predecessors[_target[i]];) while _target[i] != _source.<br>
<blockquote cite="mid:4FF717D9.8040401@swoodbridge.com" type="cite">
<br>
Thanks,
<br>
-Steve W
<br>
</blockquote>
Thanks to you for the feedbacks!<br>
<blockquote cite="mid:4FF717D9.8040401@swoodbridge.com" type="cite">_______________________________________________
<br>
Pgrouting-users mailing list
<br>
<a class="moz-txt-link-abbreviated" href="mailto:Pgrouting-users@lists.osgeo.org">Pgrouting-users@lists.osgeo.org</a>
<br>
<a class="moz-txt-link-freetext" href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a>
<br>
</blockquote>
<br>
<br>
</body>
</html>