Patent ID: 7941778

Claim:
A computer-implemented method comprising: representing a network using a graph, the graph comprising a plurality of vertices and a plurality of edges, the plurality of vertices comprising a source vertex, a destination vertex and a vertex u, the plurality of edges linking corresponding adjacent pairs of the plurality of vertices, the plurality of edges comprising edges corresponding to existing fiber optic cables; augmenting the graph with additional edges representing potential new fiber optic cables such that an additional edge is added between any pair of adjacent vertices directly connected by an edge corresponding to one of the existing fiber optic cables, the additional edge having a cost corresponding to the cost of laying the new fiber optic cable; and determining, in a processor, a minimum cost path in the graph from the source vertex to the destination vertex, wherein the vertex u is in the minimum cost path, and wherein an edge from the vertex u in the minimum cost path introduces an additional capital expenditure cost that is dependent on how the minimum cost path traverses from the source vertex to the vertex u.