Yen's algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /yen-algorithm#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /yen-algorithm#noredirect を利用してください。
name
Yen's algorithm
short description
Yen's algorithm とは、与えられたグラフ $G$ の $s-t$ 単純路であって $K$ 番目に短いものを $O(K V (E + V) \log V)$ で求めるアルゴリズムである。
input
有向あるいは無向グラフ $G$ とその頂点 $s, t$ および自然数 $K$
output
$G$ の $s-t$ 単純路であって $K$ 番目に短いもの
time complexity
$O(K V (E + V) \log V)$