For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A k-Best Paths Algorithm for Highly Reliable Communication Networks
Shi-Wei LEE Cheng-Shong WU
IEICE TRANSACTIONS on Communications
Publication Date: 1999/04/25
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Communication Networks and Services
k-best paths, disjoint paths, reliable network design,
Full Text: PDF>>
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.