Two Algorithms for the k-Widest Path Problem

摘要

Abstract In communication networks where services require a certain amount of bandwidth for setting up a connection, an important problem (to be referred to as the k-widest path problem) is to enumerate paths in non-increasing order of the bandwidth availability of the paths. For this problem, a path follows a non-additive, concave cost property. Notably, this problem parallels the k-shortest path problem for which the path cost is additive. We present two exact algorithms for solving this problem, denoted by kWP-1 and kWP-2, inspired by the loopless version of MPS (Martins–Pascoal–Santos) algorithm and Yen’s algorithm for the k-shortest path algorithm, respectively. Our numerical study shows that kWP-2 is more effective than kWP-1 for the k-widest path problem, in contrast with the relatively better performance of MPS over Yen’s algorithm regarding the enumeration of k-shortest paths.