全頂点間最短パス問題に対するアルゴリズムの実験的評価
スポンサーリンク
概要
- 論文の詳細を見る
全頂点間最短パスは連続する行列積の計算に基づいてO(n^3)の計算時間で求められるが,辺の長さが整数のグラフに対してこれを実行すると計算の途中で大きな整数を扱わなければならないことになる.実際,最初の行列の要素の最大値がMならば,最後の行列の最大値は(n-1)Mとなりうる.これに対して,途中の計算で生じる整数を高々2Mとしながらより高速に全頂点間最短パスを求めるアルゴリズムが最近提案されている.本稿では辺の長さが整数の全頂点間最短パス問題に対して最近提案された高速アルゴリズムの簡略版を実装し,予備的な計算機実験を通して実際的性能の評価を行う.
- 社団法人電子情報通信学会の論文
- 2001-03-09