説明 グラフ G と始点終点の対 (s,t) が与えられたとき,s-t パスの中で k 番目に短いものを求める問題を k-最短路問題という. この問題に対する最も基本的な解法は,優先度付きキューを用いてダイクストラ調にグラフを探索し,通常なら最短距離が確定した頂点を切り捨てるところを k 個の最短距離が確定した頂点を切り捨てるようにすることである(以下に実装を示した).この方法で計算量 O(k E log V) が達成できる.多くの応用ではこれで十分だと考えられる. 理論的にはもっと頭の良い解法が提案されており,例えば Eppstein による deviation に基づくアルゴリズムは O(k + E + V log V) を達成する.しかし,このアルゴリズムはパスを管理するデータ構造を持たなければならず,シンプルに実装するのは難しい.そこで以下では Eppstein の方法を参考にした