Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!ads.com!sparkyfs.erg.sri.com!vlad
From: vlad@erg.sri.com (vlad)
Newsgroups: comp.theory
Subject: Re: K shortest paths
Message-ID: <1991Apr24.181720.22739@erg.sri.com>
Date: 24 Apr 91 18:17:20 GMT
References: <1991Apr19.002449.28518@cbnewsk.att.com>
Sender: news@erg.sri.com
Organization: SRI International, Menlo Park, CA
Lines: 36

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