Constrained shortest path algorithms for network control

Abstract

This paper considers networks consisting of links with variable "lengths" and problems requiring to select, between a pair of nodes, the shortest path under a constraint. More specifically, we determine the shortest paths under the constraint from a source node to all other nodes. Examples of the constraints and criteria of analysis are provided. Two different classes of the constraint-shortest-path problems are introduced. Two algorithms are presented (CSPA-1 and CSPA-0), and the analysis of their complexities is provided. Examples of applications for control and design of communication networks are considered. Two numerical examples are provided. It is demonstrated that both algorithms have polynomial complexities of the same order.