Efficient Methods to Determine Disjoint Paths for Single Demands

This chapter concentrates on computationally efficient methods for determining the shortest sets of disjoint communication paths for single demands. It discusses the properties of computationally efficient methods for determining the shortest sets of k end-to-end disjoint communication paths crucial in assuring protection against simultaneous failures of \(k-1\) network elements. For this purpose, it starts with explaining the details of the common Dijkstra’s algorithm for calculating the shortest path between a particular pair of end nodes, as this algorithm plays an essential role in the operation of other algorithms discussed in this chapter. Next, it explains and illustrates the most representative schemes to determine a shortest set of disjoint paths in single-cost networks, namely, Suurballe’s and Bhandari’s algorithms. Finally, it discusses the properties of the k-Penalty algorithm designed to determine the set of k end-to-end disjoint paths in networks with different costs assigned to links for the calculation of different paths (i.e., the so-called “multi-cost” network case).