Topkis, Donald M. A k shortest path algorithm for adaptive routing in communications networks. (English) Zbl 0654.90021 IEEE Trans. Commun. 36, No. 7, 855-859 (1988). The problem of finding k shortest loopless paths with distinct initial links from one node to each other node arises in several important contexts for adaptive routing in communication networks. One context is the construction or adaptive reconstruction of routing tables where a sequential routing algorithm is used, and another context is “delta routing”. This paper presents an efficient and flexible algorithm for this k shortest path problem. Low-order polynomial bounds are established for the worst case time complexity of the algorithm, showing it to offer a substantial improvement over applying known algorithms to the problem. The algorithm can incorporate various extensions, including the ability to handle an algebraic objective, which enhance its applicability to diverse network models. In addition, the present k shortest path formulation and algorithm are proposed as a basis for network survivability measures where path length bounds exist. Cited in 3 Documents MSC: 90B10 Deterministic network models in operations research 90B35 Deterministic scheduling theory in operations research 68Q25 Analysis of algorithms and problem complexity 90C35 Programming involving graphs or networks Keywords:shortest loopless paths; adaptive routing; communication networks; delta routing; Low-order polynomial bounds; worst case time complexity; network survivability measures × Cite Format Result Cite Review PDF Full Text: DOI