ACCELERATING THE SHORTEST PATH PROBLEM

The solution to the shortest path between a source node and multiple destination nodes is accelerated using a grouping of nodes, where the nodes are grouped based on distance from the source node, and a corresponding set of memory locations that indicate when a group includes one or more nodes. The memory locations can be quickly searched to determine the group that represents the shortest distance from the source node and that includes one or more nodes. Nodes may be grouped into additional groupings that do not correspond to the set of memory locations, when the distance from the source node to the nodes exceeds the range of memory locations. Advantageously, the disclosed system and method provide the ability to reach asymptotically optimal performance.