Patent ID: 8144626

Claim:
A method comprising: receiving a graph representing a network comprising a plurality of nodes and a plurality of links; transforming the graph such that the number of intermediate nodes of a path indicates the number of regenerators for the path; generating a set of one or more seed paths from a source node to a destination node of the transformed graph; for each seed path of a subset of the seed paths, determining using a processor a shortest path from the source node to the destination node to yield a pair of disjoint paths from the source node to the destination node, the determining the shortest path comprising: adding one or more fast links, a fast link indicating a possible overlap segment between the each seed path and the shortest path; and assigning a fast link cost to each fast link, the cost of a fast link indicating an additional number of regenerators on both the shortest path and the each seed path if an overlap occurs; and selecting an optimized pair of disjoint paths from the pairs of disjoint paths, the optimized pair of disjoint paths having an optimized number of regenerators.