Re: [Boost-users] [Graph] How to do multi source shortest path

Subject: Re: [Boost-users] [Graph] How to do multi source shortest path
From: Leo Cacciari (leo.cacciari_at_[hidden])
Date: 2012-03-07 10:44:05

Il 03/07/2012 04:22 PM, Gordon Woodhull ha scritto:
> 
> 
> On Mar 7, 2012, at 8:27 AM, Leo Hidd <leohidd_at_[hidden]> wrote:
> 
>> and how do I create this "super source" vertex? The dijkstra_shortest_paths function takes only one vertex_descriptor, not an array of it (isn't it?).
> 
> I meant, just add a special vertex to your graph and connect it with zero-weight edges to all the sources you want, and specify that as the source. Requires a little bit of detective work at the end to see which source a path goes through, but it should get you your answer.
> 
This, by the way, is the "classical" graph-theoretical way to address
your problem _and_ becomes your idea of putting all the source vertices
into the queue at the start, as _this_ is _exactly_ what would do the
djikstra algorithm upon finding a source connected with 0-length edges
to a bunch of other vertices. (just my 5¢)

L.C.

-- 
Leo Cacciari
Aliae nationes servitutem pati possunt populi romani est propria libertas