Disjoint paths in a network

Abstract

Routes between two given nodes of a network are called diversified if they are node‐disjoint, except at the terminals. Diversified routes are required for reliability in communication, and an additional criterion is that their total cost, assumed to be the sum of individual arc lengths or costs, is minimum. An algorithm and related theory is described for a general number K of node‐disjoint paths with minimum total length. The algorithm applies shortest path labeling algorithms familiar in the literature. K node‐disjoint paths are found in K iterations of a single shortest path algorithm.