SYSTEMS AND METHODS FOR MULTI-DESTINATION CONTRACTION HIERARCHY PATH SEARCH

A system described herein may efficiently perform a multi-destination backward search, which may be a part of performing a bidirectional search in a node map that implements contraction hierarchy techniques. Lowest cost paths to each node reachable to each destination node of a set of destination nodes may be computed. A queue may be initialized with the set of destination nodes. For each particular node in the queue, the system may add higher priority neighbors of the particular node to the queue, identify costs of outgoing links from the particular node to the higher priority neighbors, compute lowest cost paths associated with the set of destination nodes based on the identified costs of outgoing links from the particular node to the higher priority neighbors and any previously computed lowest cost paths associated with the set of destination nodes, and increment to a next node in the queue.