The MPLS WG Archive

["Awduche, Daniel" <awduche@movaz.com>]

The 'K-Shortest Path' problem is well known and
well studied (dating back to the late 1950's).
Many different versions of this problem exist, 
subject to various types of restrictions.

There are solution techniques based on improvements
to Dijkstra's algorithm, and many others based 
on network flows and dynamic programming methods.
Some approaches involve elegant graph transformations
(as was the case, for example, in Ramesh's book on 
diverse routing).

In addition to the references mentioned by Ramesh, 
the works of David Eppstein (and the references
therein) may be of interest:
<http://www.ics.uci.edu/~eppstein/pubs/all.html>. 

CAVEAT:-- Many theoretical versions of the K-Shortest
Path problem do not require the paths to be simple 
(i.e. loop-free). 

Yes, the K-Shortest Path problem may have relevance in
optical connection routing, especially when considering
wavelength assignment, optical impairments, and other
constraints.

Cheers,
/Dan  


> -----Original Message-----
> From: Ramesh Bhandari [mailto:bhandari@hotair.hobl.lucent.com]
> Sent: Tuesday, August 14, 2001 1:37 PM
> To: Chrysostomos Tziouvaras
> Cc: mpls-ops@mplsrc.com; mpls@UU.NET; IP-Optical@lists.bell-labs.com
> Subject: [IP-Optical] Re: An algorithm for calculating all 
> paths between
> an s-d pair
> 
> 
> Hi Chrysostomos,
> 
> I believe you are searching for the K-shortest path algorithm, which
> provides paths for a given pair of nodes in ascending order of their
> lengths. An example website for information on this is
> http://www.mat.uc.pt/~eqvm/cientificos/investigacao/r_papers.html#mps.
> 
> But, if you are looking for algorithms for K-disjoint paths, these can
> be found in my book: "Survivable Networks: Algorithms for Diverse
> Routing", Kluwer Academic Publishers (1999).
> 
> Regards,
> 
> Ramesh
> 
> Chrysostomos Tziouvaras wrote:
> > 
> > Hi,
> > I am searching for an algorithm for calculating all paths 
> between an s-d
> > pair. Can you provide me pointers to books or URLs?
> > 
> > Thanks
> > Chrysostomos
> 
> _______________________________________________
> IP-Optical mailing list
> IP-Optical@lists.bell-labs.com
> http://lists.bell-labs.com/mailman/listinfo/ip-optical
>