Given the graph of a network with a distance (cost) assigned to each link, shortest path algorithms find the least cost path between a selected node and all other nodes in the network [Bertsekas98, Gibbons85].
Before we delve into the applicability of this technique to optical path selection, we first need to introduce some terminology and notation. A network can be represented by a graph G = (N, A), where N is the set of nodes (also called vertices) and A is the set of links. (i, j)∊ A, if there is a link from node i to node j. Note that for complete generality, each link is considered to be unidirectional. If a link from node i to node j is bi-directional, then (i, j)∊ A and (j, i)∊ A. For a link (i, j)∊ A,