最短経路と最長経路問題について

グラフの2頂点間の最短経路を算出する問題は多項式時間問題である。ところが，2点を結ぶ最も長い経路を求める問題は，最短経路問題と似ているが，NP完全問題であり，多項式時間で解けるかどうかは分かっていない。この例をもとに，NP完全問題について論じた。

パソコンリテラシ

第25巻第10号,11-16