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 Hidd (leohidd_at_[hidden])
Date: 2012-03-07 12:41:04

Le 07/03/2012 16:44, Leo Cacciari a écrit :
> 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.
>
y, yes, but what i meant was, like, pass an array (or vecS) as argument 
to dijkstra_shortest_paths whose size is the number of nodes of the 
graph and this array would be filed with the index of the closest 
source. By the way, the distance and path arrays are relative to the 
closest source. The idea of tracking back through the path is always a 
solution to it, but it is more computational complex than storing the 
result direct to an array.

I'll try Gordon's suggestion. I come back with results. In the mean time 
I'm also trying to create a test case for Jeremiah on the other topic 
"[Graph] How to do multi source shortest path".

thx guys, leo