Am Sonntag, 8. Januar 2006 17:11 schrieb Xavier Noria:

> I would like to compute the shortest path between A and C passing

> through B. As far as I can tell that is the shortest path between A

> and B joined with the shortest path between B and C.

>

> Is there a known especific algorithm to compute that (albeit maybe

> not in the current API)? Or should I just build it from two calls to

> findPathBetween following the former remark? Efficiency is important

> in this application.

You could simply use the ClosestFirstIterator, starting from B and iterate the

vertices until you find A and C. This will work only for an undirected graph

where the shortest path from A to B is equal to the shortest path from B to

A. Furthermore joining two paths does not neccessarily create a path

(depending on your definition of path) because vertices and edges may be

used multiple times. But if Your "path" is allowed to do so you can

reconstruct the two paths the same way it is done in

DijkstraShortestPath.createEdgeList.

Yours,

Michael

P.S: If performance is really critical and you do not need the full power of

java collections strongly consider reimplementing it.

--

Michael Behrisch (Tel. +49 30 2093-3123)

HU Berlin, Institut fuer Informatik, Arbeitsgruppe Algorithmen

http://www.informatik.hu-berlin.de/~behrisch/