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

Yasui Yuichiro, Fujisawa Katsuki, Sasajima Hiroshi, Goto Kazushige

doi:10.15807/torsj.54.58

Bibliographic Information

Other Title

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

Search this article

Description

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

Transactions of the Operations Research Society of Japan

Transactions of the Operations Research Society of Japan 54 (0), 58-83, 2011

The Operations Research Society of Japan

Keywords

Details 詳細情報について

Export

Report a problem