Quantcast

shortest path passing through

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

shortest path passing through

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.

-- fxn



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: shortest path passing through

Michael Behrisch
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/

attachment0 (189 bytes) Download Attachment
Loading...