Survey of Speedup Techniques for Shortest Path Algorithms

The problem of efficient path computation arises in many domains of practical importance. Classical algorithms failed to apply to large-scale networks due to their heavy computational complexity. This paper reviews some latest representative results classified according to the underlying speedup techniques, including basic speedup techniques like priority queues, goal-directed techniques, and hierarchical approaches. Moreover, the paper introduces the most recent achievement of the authors on network hierarchy construction and hierarchical algorithm design. Finally, some future directions are discussed.