lor@cbnewsk.att.com (edward.lor) (04/19/91)
Are there any established algorithms to find the k (k>1) shortest paths
between two nodes in a graph?
When k=1, there are numerous algorithms to the problem (Dijkstra's,
breadth-first, etc.), but I can't find any materials in finding k paths
in most of the graph theory books.
Any pointer is appreciated.
--
Edward Lor
lor@cbnewsk.att.com
vlad@erg.sri.com (vlad) (04/25/91)
In article <1991Apr19.002449.28518@cbnewsk.att.com> lor@cbnewsk.att.com (edward.lor) writes: > >Are there any established algorithms to find the k (k>1) shortest paths >between two nodes in a graph? > >When k=1, there are numerous algorithms to the problem (Dijkstra's, >breadth-first, etc.), but I can't find any materials in finding k paths >in most of the graph theory books. > >Any pointer is appreciated. > >-- > Edward Lor > lor@cbnewsk.att.com > Here are some: \bibitem{sur74} J.W. Suurballe. \newblock Disjoint paths in a network. \newblock {\em Networks}, 4:125--145, 1974. For k=2: \bibitem{surtar84} J.W. Suurballe and R.E. Tarjan. \newblock A quick method for finding shortest pairs of disjoint paths. \newblock {\em Networks}, 14:325--336, 1984. Richard Ogier, Nachum Shacham and I have recently submitted for publication a paper on distributed solutions to this problem. I can send you a copy. Vlad Rutenburg