大規模最短路問題に対するダイクストラ法の高速化

The shortest path problem can be widely applied not only to route search in large-scale network but to other optimization problems where the shortest path problems are used as subproblems. Although there exist stable and efficient algorithms for the shortest path problem, we need fast implementations when solving large-scale shortest path problems. In this paper, we discuss how to make fast and general implementations of Dijkstra's algorithm, where the memory hierarchy is carefully considered to specify the bottleneck of the algorithm and to improve the performance. Our implementations with the binary heap are superior to other existing implementations when taking three factors (performance, robustness, and required computational memory) into consideration. We show that our implementations can get optimal routes very quickly and require smaller computational memory compared with other implementations through systematic numerical experiments. We also explain the Web service for large-scale shortest path problems, which employs our implementations.