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