Re: [jgrapht-users] shortest path passing through

[Michael B. <beh...@in...>]

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=20
vertices until you find A and C. This will work only for an undirected grap=
h=20
where the shortest path from A to B is equal to the shortest path from B to=
=20
A. Furthermore joining two paths does not neccessarily create a path=20
(depending on your definition of path) because vertices and edges may be=20
used multiple times. But if Your "path" is allowed to do so you can=20
reconstruct the two paths the same way it is done in=20
DijkstraShortestPath.createEdgeList.

Yours,
Michael

P.S: If performance is really critical and you do not need the full power o=
f=20
java collections strongly consider reimplementing it.
=2D-=20
Michael Behrisch (Tel. +49 30 2093-3123)
HU Berlin, Institut fuer Informatik, Arbeitsgruppe Algorithmen
http://www.informatik.hu-berlin.de/~behrisch/