Patent ID: 7719960

Claim:
A method of minimizing path values associated with paths in a network comprising, in a router: storing a data structure on a computer-readable medium, the data structure defining a network of nodes and links where the links have at least one weight between nodes; storing plural data sets, each data set corresponding to paths, including potential loop-free and potential U-turn alternate paths, that yield solutions of a minimization function that gives a path with a minimum path value, and each element of the data set containing a path value that corresponds to a solution for a particular node of the network for that minimization function; and for the plural data sets, maintaining a common set of candidate nodes having path values to be inherited by other nodes; and successively selecting nodes from the set of candidate nodes and, when a change flag indicates a change in the path value to be considered for inheritance, computing path values of nodes neighboring the selected nodes from path values of the selected nodes and weight values from functions of traversed links; and updating any path value which has been further reduced for a node neighboring the selected node and then adding that node to the common set of candidate nodes if that node is not already in that set.