Routing, Flow, and Capacity Design in Communication and Computer Networks

APPENDIX C

Shortest-Path Algorithms

C.1 INTRODUCTION AND BASIC NOTIONS

Algorithms for the basic problem of finding the shortest path P between vertices in a graph with edges of non-negative weights are well known, especially the Dijkstra’s algorithm. Still, more sophisticated algorithms solving certain modifications of the basic problem, important for this book, are not so widespread. Therefore, in this appendix, we present a selected set of algorithms useful for computing sets of shortest paths with certain desirable properties. These algorithms are needed for generating candidate path lists for the network design problems in link-path formulation used extensively throughout the book. We will start with presenting Dijkstra’s algorithm for ...