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