Hierarchical speed-up techniques for shortest-path algorithms
Martin Hölzer · KOPS (University of Konstanz) · 2003
Shortest-path problems occur in many fields of application, where the graphs are often very large and queries have to be answered in 'real-time'. This cannot be overcome by the classical algorithm of Dijkstra but requires more sophisticated speed-up techniques. One approach consists of hierarchical decomposition of a given graph and pre-computation of information in order to reduce search space during the on-line stage. One such technique applied to a specific scenario was recently investigated in a systematic experimental study. In the following work, we follow up and give a detailed analysis of this speed-up technique along with experiments using several graph classes.