Accelerating the shortest path problem
AssigneeApplied Micro Circuits Corporation
InventorCedell Alexander
Life of this patent
Estimating the term…
Abstract
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.
Claims21
An apparatus comprising:
- a set of memory locations;
- a plurality of groups, each group comprising zero or more nodes, each group being associated with a memory location, said memory location containing a valid value if the group contains one or more nodes;
- and
- a lookup circuit for finding a valid value in said set of memory locations at the highest priority address of said set of memory locations.
A method comprising:
- grouping nodes into a plurality of groups based on an attribute;
- initializing a set of memory locations, which contains one location for each group, by setting at least one bit in a memory location if the corresponding group contains at least one node;
- selecting a group with the attribute with the highest priority and having at least one node using said set of memory locations;
- and
- supplying a node from said selected group, wherein supplying comprises retrieving a node from said selected group and deleting said node from said selected group.
A method of finding the shortest path between a source node and multiple destination nodes, said method comprising:
- evaluating nodes that neighbor a first node based on the distance from the source node to the neighboring nodes;
- grouping the neighboring nodes into a plurality of groups based on the distance from the source node to the neighboring nodes;
- initializing a set of memory locations, which contains one location for each group, by setting at least one bit in a memory location if the corresponding group contains at least one node;
- selecting a group having at least one node, said group representing the shortest distance from the source node;
- retrieving the next node from said selected group and deleting said node from said selected group.
Dependencies are inferred from the claim text.