PRACTICAL EFFICIENCY OF THE LINEAR-TIME ALGORITHM FOR THE SINGLE SOURCE SHORTEST PATH PROBLEM
-
- Asano Yasuhito
- Graduate School of Information Science, The University of Tokyo
-
- Imai Hiroshi
- Department of Information Science, University of Tokyo
この論文をさがす
抄録
Thorup's linear-time algorithm for the single source shortest path problem consists of two phases: a construction phase of constructing a data structure suitable for a shortest path search from a given query source s; and a search phase of finding shortest paths from the query source s to all vertices using the data structure constructed in construction phase. Since once the data structure is constructed, it can be repeatedly used for shortest path searches from given query sources, Thorup's algorithm has a nice feature not only on its linear time complexity but also on its data structure suitable for a repetitive mode of queries (not single query). In this paper, we evaluate the practical efficiency of the Thorup's linear-time algorithm through computational experiments comparing with some of well known previous algorithms. In particular, we evaluate Thorup's algorithm mainly from the viewpoint of repetitive mode of queries.
収録刊行物
-
- 日本オペレーションズ・リサーチ学会論文誌
-
日本オペレーションズ・リサーチ学会論文誌 43 (4), 431-447, 2000
公益社団法人 日本オペレーションズ・リサーチ学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282679085347584
-
- NII論文ID
- 110001183926
-
- NII書誌ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
- http://id.crossref.org/issn/04534514
-
- NDL書誌ID
- 5599912
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- NDL
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可