algorithm - 哈密​​顿路径与最短路径

Question

在研究了这两个问题之后，我无法得出它们之间有什么区别。

哈密​​顿路径

哈密​​顿路径是图的两个顶点之间的路径，每个顶点恰好访问一次。给定一个图G和两个不同的节点S和，从到E是否有哈密顿路径？GSE

我发现这个问题是NP-Complete

最短路径

在图论中，最短路径问题是在图中找到两个顶点（或节点）之间的路径，使得其组成边的权重之和最小化的问题。这个问题是P

它们之间的实际区别是什么？它们的复杂性是如何计算的？

Answer 1

The Hamiltonian Path problem is actually looking for a longest simple path in a graph. It is easy to see that the two problems are basically equivalent (longest simple path and hamiltonian path). This problem is indeed a classic NP-Complete Problem.
It is NP-Complete since there is a polynomial reduction from another (already proved) NP-Hard Problem to this problem, and thus (from transitivity of polynomial reductions) this problem is NP-Hard as well. Since it is also in NP, it is NP-Complete.

The shortest path on the other hand is a different one, it asks what is the shortest way from point A to point B, and it is in P because there is a polynomial time algorithm that solves it (Dijkstra's algorithm, Bellman-Ford, BFS for non weighted graphs).

---

Regarding "And how is there complexity calculated?" I assume you mean how do we determine their complexity classes - in this case, Shortest Path is in P because we have a deterministic polynomial time algorithm that solves it (some mentioned above), while the complexity class of Hamiltonian Path is NP-Complete because it is both NP-Hard (there is polynomial reduction from another proven NP-Hard problem), and NP (we can solve it easily in polynomial time on non-determinitic turing machine).
Note that we DO NOT KNOW if Hamiltonian Path is in P or not, because we do not know if P=NP.

Answer 2

任意节点间最长路径和最短路径的区别在于最短路径问题有一个最优子结构，因此可以用动态规划求解；最长路径问题没有最优子结构，无法使用动态规划求解。如果可以从其子问题的最优解构造最优解，则称该问题具有最优子结构。例子

一个例子就是上图。从 q 到 t 的最短路径包括从 q 到 r 的最短路径。但是q到t的最长路径是qrt，q到r的最长路径是qstr，不包含在qrt中。这是因为最长路径的子问题不是相互独立的。从 q 到 r 的最长路径是 qsrt。从 r 到 t 的最长路径是 rqst。这两个问题有重叠，所以它们不是独立的，所以这个问题没有最优子结构，所以不能用动态规划和贪心算法来解决。