[Lemon-user] Dijkstra's on multiple source shortest path

[Alpar Juttner]

Hi,

> When I read Dijkstra's algorithm in Lemon
> (http://lemon.cs.elte.hu/pub/tutorial/a00010.html#sec_shortest_paths),
> I found it can add additional source by 
> dijkstra.addSource(s);
> But I don't quite understand what the definition of the multiple
> source shortest path (MSSP).

What you get is basically equivalent to adding and auxiliary node s to
the graph then connecting s to each source node with a zero length arc.

>  Do I get a distance map, where each target node have a minimal
> distance over the possible path from multiple sources?

Yes. In addition the "prev" map will form couple of node disjoint trees,
each rooted at one of the sources.

> Also what is the computation time of the multiple source problem
> compared to the single source one? 

The same as the normal Dijkstra. E.g. using the default binary heap the
worst case running time is O(mlogn+n+logn), where n is the number of
nodes and m is the number of arcs.

> A quick search online gave me results of the MSSP on planar graph. Is
> it a well defined problem for general directed graph? 

Yes it is, just as I wrote above.

Regards,
Alpar

> 
> 
> Thanks,
> Wei
> University of Utah
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user