■

k-shortest pathで、MPS法というのがある。ノードを複製していくときに、アークは増やさない実装とアークを増やす実装をしたら、アークを増やす方が早かった。ちなみに、格子状の100万ノードで10本求めるのに5秒くらいだ。
普通に実装するとループの経路がみつかる。もっといい方法があるのかも。