wikipedia見ながら考えてる素人だけど
>>87ってホントにNP困難なのかなー

任意のグラフじゃなく格子状のグラフなのに難しそうだからって
NP困難って決め付けるのは早計だと思う

NP完全って言ってる人は信用できないし
(経路を求める問題だからNPに属してないでしょ？)