Systems and methods for multi-destination contraction hierarchy path search

A non-transitory computer-readable medium, storing a plurality of processor-executable instructions to:

• receive a node map that includes a set of nodes and respective links between nodes, wherein each node is associated with a respective measure of priority and wherein each link is associated with a respective cost;
• identify a set of destination nodes in the node map;
• initialize a queue by adding the set of destination nodes to the queue;
• compute lowest cost paths to each node reachable to each destination node of the set of destination nodes,
• wherein a first iteration of the computing includes, for a first node in the queue:
• adding higher priority neighbors of the first node, which are not in the queue, to the queue;
• loading, to a memory device, information indicating costs of outgoing links from the first node to the higher priority neighbors of the first node;
• and
• performing a first iteration of computing lowest cost paths associated with the set of destination nodes based on:
• the costs of the outgoing links from the first node to the higher priority neighbors of the first node, and
• any previously computed lowest cost paths associated with the set of destination nodes,
• wherein a second iteration of the computing includes, for a second node that is a next node in the queue with respect to the first node:
• loading, to the memory device, information indicating costs of outgoing links from the second node to higher priority neighbors of the second node, without loading the information indicating the costs of outgoing links from the first node to the higher priority neighbors of the first node;
• and
• performing a second iteration of computing lowest cost paths associated with the set of destination nodes based on:
• the costs of the outgoing links from the second node to the higher priority neighbors of the second node, and
• any previously computed lowest cost paths associated with the set of destination nodes, including one or more lowest cost paths computed when performing the first iteration of computing the lowest cost paths;
• receive a navigation request for a route between a particular starting node in the node map and a particular destination node of the set of destination nodes;
• generate the requested route based on a particular computed lowest cost path associated with the particular destination node;
• and
• output, in response to the navigation request, the generated route.

A method, comprising:

• receiving a node map that includes a set of nodes and respective links between nodes, wherein each node is associated with a respective measure of priority and wherein each link is associated with a respective cost;
• identifying a set of destination nodes in the node map;
• initializing a queue by adding the set of destination nodes to the queue;
• computing lowest cost paths to each node reachable to each destination node of the set of destination nodes,
• wherein a first iteration of the computing includes, for a first node in the queue:
• adding higher priority neighbors of the first node, which are not in the queue, to the queue;
• loading, to a memory device, information indicating costs of outgoing links from the first node to the higher priority neighbors of the first node;
• and
• performing a first iteration of computing lowest cost paths associated with the set of destination nodes based on:
• the costs of the outgoing links from the first node to the higher priority neighbors of the first node, and
• any previously computed lowest cost paths associated with the set of destination nodes,
• wherein a second iteration of the computing includes, for a second node that is a next node in the queue with respect to the first node:
• loading, to the memory device, information indicating costs of outgoing links from the second node to higher priority neighbors of the second node, without loading the information indicating the costs of outgoing links from the first node to the higher priority neighbors of the first node;
• and
• performing a second iteration of computing lowest cost paths associated with the set of destination nodes based on:
• the costs of the outgoing links from the second node to the higher priority neighbors of the second node, and
• any previously computed lowest cost paths associated with the set of destination nodes, including one or more lowest cost paths computed when performing the first iteration of computing the lowest cost paths;
• receiving a navigation request for a route between a particular starting node in the node map and a particular destination node of the set of destination nodes;
• generating the requested route based on a particular computed lowest cost path associated with the particular destination node;
• and
• outputting, in response to the navigation request, the generated route.