[pgrouting-users] One_To_Many dijkstra

[HSylvio]

On 7/6/2012 6:52 PM, Stephen Woodbridge wrote:
> On 7/6/2012 10:00 AM, Sylvain Housseman wrote:
>> Dear pg_routers,
>>
>> I added a page describing my first (very minor) contribution to the 
>> wiki:
>> https://github.com/pgRouting/pgrouting/wiki/One_to_many-Dijkstra---To-review 
>>
>>
>>
>> I don't know how to make it accessible (and at first if the function
>> really is relevant, I believe that many of you coded a similar
>> function...).
>> As soon as it does not really modify the method (boost_dijkstra), I
>> think the Algorithms section is not appropriate.
>>
>> Should I
>> - remove the whole stuff?
>> - add a new section to https://github.com/pgRouting/pgrouting/wiki (i.e.
>> "Optional wrappers" or "Contrib. / betas")?
>>
>> Please feedback if you have the time to try it;
>
> Hi Sylvain,
>
> Thank you for your contribution. It is very much appreciated.
>
> I have a question, if I have 10 destination nodes, how many times to 
> you solve the graph after it is built?
Only once...
>
> 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.
>
> Is this how your algorithm works?
I wouldn't have explained it better!

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);"
and after the resolution, I loop on nb_targets to build the paths as 
/rewinding/ on the tree (_target[i] = predecessors[_target[i]];) while 
_target[i] != _source.
>
> Thanks,
>   -Steve W
Thanks to you for the feedbacks!
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20120706/4806599d/attachment.html>