著者

浅野 泰仁 今井 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1998, no.41, pp.1-8, 1998-05-20

参考文献数

6

---

単一始点最短路問題(SSSP)を解くためのアルゴリズムとしては、Dijkstraのアルゴリズムが有名である。過去、Dijkstraのアルゴリズムを高速化する研究が多く行われてきたが、ソート問題に相当するボトルネックのため、線形時間を達成することはできなかった1997年、M.Thorupが整数枝重み無向グラフでのSSSPを線形時間で解くアルゴリズムを発表した。しかしこのアルゴリズムで使用されている複雑なデータ構造のいくつかは理論通りには実装できない。本研究では、Thorupのアルゴリズムを現在の計算機上で実装するための変更を提案した上で、実際にThorupのアルゴリズムの実装をおこなった。さらに、既存のアルゴリズムとの比較実験および各部分の実行時間計測をおこなった。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.