A k-Best Paths Algorithm for Highly Reliable Communication Networks

Shi-Wei LEE  Cheng-Shong WU  

IEICE TRANSACTIONS on Communications   Vol.E82-B   No.4   pp.586-590
Publication Date: 1999/04/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Communication Networks and Services
k-best paths,  disjoint paths,  reliable network design,  

Full Text: PDF>>
Buy this Article

In highly reliable communication network design, disjoint paths between pairs of nodes are often needed in the design phase. The problem of finding k paths which are as diverse as possible and have the lowest total cost is called a k-best paths problem. We propose an algorithm for finding the k-best paths connecting a pair of nodes in a graph G. Graph extension is used to transfer the k-best paths problem to a problem which deploits well-known maximum flow (MaxFlow) and minimum cost network flow (MCNF) algorithms. We prove the k-best paths solution of our algorithm to be an optimal one and the time complexity is the same as MCNF algorithm. Our computational experiences show that the proposed algorithm can solve k-best paths problem for a large network within reasonable computation time.