WEKO3
-
RootNode
アイテム
単一始点最短路問題（SSSP）線形時間アルゴリズムの実際的評価
https://ipsj.ixsq.nii.ac.jp/records/32179
https://ipsj.ixsq.nii.ac.jp/records/32179c17fea3d-08aa-49c3-8d14-12aaad69891e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL98062001.pdf (564.7 kB)
|
Copyright (c) 1998 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1998-05-20 | |||||||
| タイトル | ||||||||
| タイトル | 単一始点最短路問題（SSSP）線形時間アルゴリズムの実際的評価 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Practical evaluation of a linear - time algorithm for the single source shortest path problem (SSSP) | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京大学大学院理学系研究科情報科学 | ||||||||
| 著者所属 | ||||||||
| 東京大学大学院理学系研究科情報科学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Science, University of Tokyo | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Science, University of Tokyo | ||||||||
| 著者名 |
浅野, 泰仁
今井, 浩
× 浅野, 泰仁 今井, 浩
|
|||||||
| 著者名(英) |
Yasuhito, Asano
Hiroshi, Imai
× Yasuhito, Asano Hiroshi, Imai
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 単一始点最短路問題(SSSP)を解くためのアルゴリズムとしては、Dijkstraのアルゴリズムが有名である。過去、Dijkstraのアルゴリズムを高速化する研究が多く行われてきたが、ソート問題に相当するボトルネックのため、線形時間を達成することはできなかった1997年、M.Thorupが整数枝重み無向グラフでのSSSPを線形時間で解くアルゴリズムを発表した。しかしこのアルゴリズムで使用されている複雑なデータ構造のいくつかは理論通りには実装できない。本研究では、Thorupのアルゴリズムを現在の計算機上で実装するための変更を提案した上で、実際にThorupのアルゴリズムの実装をおこなった。さらに、既存のアルゴリズムとの比較実験および各部分の実行時間計測をおこなった。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | SSSP is one of the well known classic problems in graph theory and Dijkstra's algorithm for SSSP is also quite popular. Several improvements of Dijkstra's algorithm have been studied, however, they could not accomplish a linear-time owing to its sorting bottleneck. In 1997, M.Thorup proposed a linear-time algorithm for the SSSP on undirected and integer edge weight graph. However, we can not implement this algorithm naively on computers today since the data structures used in the algorithm need a word of huge length. We propose modifications to implement Thorup's algorithm and implement this algorithm. Moreover, compare execution times of the implementation and famous algorithms. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1998, 号 41(1998-AL-062), p. 1-8, 発行日 1998-05-20 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
