Patent ID: 8824337
Filing Date: 2014-09-02
Classification: G01C,H04L

Abstract:
1. A computer-implemented method for determining shortest paths between a source node and a target node in a graph comprising: determining a hierarchy of nodes with a number of levels contained in a first graph comprising a number of nodes interconnected by a number of arcs, each of the number of nodes in the hierarchy of nodes assigned to a level of the number of levels based on a priority factor of the node; calculating a first shortest path between the source node and the target node traversing a meeting node in the first graph, wherein each node in the first shortest path traverses to a node of an equal or higher level of the number of levels in the direction from the source node to the meeting node and from the target node to the meeting node; reducing the number of levels in the first graph, wherein two or more levels of the first graph are consolidated into a consolidated level to form reduced levels in a second graph, wherein a number of reduced levels in the second graph is less than the number of levels in the first graph, wherein a number of nodes and a number of arcs in the second graph is the same as the number of nodes and the number of arcs in the first graph, and wherein the nodes assigned to the two or more levels of the first graph are assigned to the consolidated level of the second graph; calculating one or more second shortest paths between the source node and the target node traversing one or more meeting nodes in the second graph, wherein each node in the second shortest paths traverses to a node of an equal or higher reduced level of the reduced levels in the direction from the source node to the meeting nodes and from the target node to the meeting nodes; and assigning the first shortest path as a primary route and the one or more second shortest paths as alternate routes.