著者

浅野 泰仁 今井 浩

雑誌

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

巻号頁・発行日

vol.1998, no.41(1998-AL-062), pp.1-8, 1998-05-20

---

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