両方の問題について調査した後、私はそれらの違いが何であるかを結論付けることはできません。
ハミルトンパス
ハミルトンパスは、グラフの2つの頂点間のパスであり、各頂点に1回だけアクセスします。Gグラフと2つの異なるノードSとが与えられた場合、からへEのハミルトン経路はありますか？GSE
この問題はNP完全であることがわかりました
最短経路
グラフ理論では、最短経路問題は、構成するエッジの重みの合計が最小になるように、グラフ内の2つの頂点（またはノード）間のパスを見つける問題です。この問題はPです
それらの実際の違いは何ですか？そして、それらの複雑さはどのように計算されますか？
ハミルトン閉路問題は、実際にはグラフ内で最も長い単純な経路を探しています。2つの問題が基本的に同等であることが簡単にわかります（最長の単純パスとハミルトンパス）。この問題は確かに古典的なNP完全問題です。
別の（すでに証明されている）NP困難問題からこの問題への多項式還元があるため、これはNP完全です。したがって、（多項式還元の遷移性から）この問題もNP困難です。NPにもあるのでNP完全です。
一方、最短経路は別の経路であり、点Aから点Bまでの最短経路を尋ねます。これを解く多項式時間アルゴリズム（ダイクストラのアルゴリズム、ベルマンフォード、BFS）があるため、Pにあります。重み付けされていないグラフの場合）。
私はあなたがそれらの複雑さのクラス"And how is there complexity calculated?"をどのように決定するかを意味すると仮定します-この場合、ハミルトニアンパスの複雑さのクラスはNP-Completeであるのに対し、私たちはそれを解決する決定論的な多項式時間アルゴリズムを持っているので、最短パスはPにありますこれは、NP困難（別の証明されたNP困難問題からの多項式削減がある）とNP（非決定的チューリングマシンで多項式時間で簡単に解決できる）の両方であるためです。
ハミルトンパスがPにあるかどうかはわからないことに注意してください。これは、 P=NPであるかどうかがわからないためです。
最長経路とノード間の最短経路の違いは、最短経路問題には最適な部分構造があるため、動的計画法で解決できることです。最長パスの問題には最適な部分構造がなく、動的計画法を使用して解決することはできません。サブ問題の最適解から最適解を構築できる場合、問題は最適部分構造を持っていると言われます。例
例は上のグラフのようになります。qからtへの最短経路には、qからrへの最短経路が含まれます。ただし、qからtへの最長パスはqrtであり、qからrへの最長パスはqstrであり、qrtには含まれていません。これは、最長パスのサブ問題が互いに独立していないためです。qからrへの最長パスはqsrtです。rからtへの最長パスはrqstです。これらの2つの問題は重複しているため、独立していないため、この問題には最適部分構造がないため、動的計画法や欲張りアルゴリズムでは解決できません。
