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

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 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