- 著者
-
新家大亮
久保田光一
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 全国大会講演論文集
- 巻号頁・発行日
- vol.2013, no.1, pp.383-385, 2013-03-06
経路探索において最短経路は一意に定まるが、2番目以降の最短経路は定義に依存して異なる。例えば、同じ点を通らない、同じ辺を通らない、同じ辺を通ってよい、などの異なる定義ができる。本研究ではこの定義をより一般的に枝や点毎に通る回数の上限を定めることとし、それに応じてHershbergerら、丸山ら、加藤ら、Eppsteinらによる4種の異なるk番目の最短経路アルゴリズムの中で適切なものを選び、k番目の最短経路を探索するライブラリを作成する。このライブラリを利用した計算実験により各アルゴリズムによる2番目以降の最短経路の比較を行う。