情報処理学会 第75回全国大会講演要旨

経路探索において最短経路は一意に定まるが、2番目以降の最短経路は
定義に依存して異なる。例えば、同じ点を通らない、同じ辺を通らない、
同じ辺を通ってよい、などの異なる定義ができる。本研究ではこの定義を
より一般的に枝や点毎に通る回数の上限を定めることとし、それに応じて
Hershbergerら、丸山ら、加藤ら、Eppsteinらによる4種の異なるk番目の
最短経路アルゴリズムの中で適切なものを選び、k番目の最短経路を探索する
ライブラリを作成する。このライブラリを利用した計算実験により各アルゴ
リズムによる2番目以降の最短経路の比較を行う。