On optimal preprocessing for contraction hierarchies

Abstract

For some graph classes, most notably real-world road networks, shortest path queries can be answered very efficiently if the graph is preprocessed into a contraction hierarchy. The preprocessing algorithm contracts nodes in some order, adding new edges (shortcuts) in the process. While preprocessing and query algorithm work for any contraction ordering, it is desirable to use one that produces as few shortcuts as possible.