Re: [jgrapht-users] DijkstraShortestPath inefficient for (start, *) ?

[kevin b. <kb...@ru...>]

On Thu, Oct 22, 2009 at 07:37:15PM -0700, John V. Sichi wrote:
> The Dijkstra API class is just a thin wrapper around 
> ClosestFirstIterator, which already provides what you need (as well as 
> the MST), though not perfectly wrapped.

John,

You're right; that's probably what I'll end up doing.

Do you think it makes sense to modify/augment JGraphT's existing Dijkstra
module to do this?  Or add a second Dijkstra implementation to JGraphT?
This seems like a common use case.

-- 
 kevin brintnall =~ /kb...@ru.../


> JVS
> 
> kevin brintnall wrote:
> > Hello,
> > 
> > JGraphT's existing Dijkstra API is able to search for a single (start,end)
> > vertex pair.  However, it doesn't appear there is a good way to calculate
> > all paths from a single source vertex: i.e. (source,*).
> > 
> > Whereas the ideal run-time of Dijkstra's algorithm is O(E + V log(V)), it
> > appears the best run-time with JGraphT's current API is O(V * ideal) for
> > this use case.
> > 
> > Maybe it's better to allow endVertex==null, and calculate the weight and
> > predecessor maps for every vertex in that case?
> > 
> > Any suggestions?  Am I missing a good alternative?
> >