FAST IMPLEMENTATION OF DIJKSTRA'S ALGORITHM FOR THE LARGE-SCALE SHORTEST PATH PROBLEM

DOI Web Site Web Site 1 Citations 28 References

Bibliographic Information

Other Title
  • 大規模最短路問題に対するダイクストラ法の高速化
  • ダイキボ サイタンロ モンダイ ニ タイスル ダイクストラホウ ノ コウソクカ

Search this article

Abstract

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.

Journal

Citations (1)*help

See more

References(28)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top