最短哈密顿路径NP是否难？

Question

Hamiltonian路径是连接所有节点而不重复的路径，它是一个NP完全问题。

1. 最短哈密顿路径（SHP）NP难吗？

2. 使用SHP的旅行推销员问题有什么区别？

Answer 1

我假设SHP问题是边缘加权图上的哈密顿问题。这是NP难的，因为它至少和汉密尔顿问题一样难。假设您有一种算法可以解决SHP问题，然后将该算法应用到所有边缘权重均为1的加权图上，它将以相同的时间复杂度解决哈密顿问题。

TSP需要返回到原始顶点，您可以一次访问每个顶点。 SHP要求访问每个顶点一次的路径。