algorithm - 是否可以使用 Dijkstra 的最短路径算法来找到最短的哈密顿路径？ (多项式时间)

Question

我读过寻找 Hamiltonian path 是否存在的问题存在于图中是 NP 完全的，并且由于 Dijkstra's Shortest Path Algorithm在多项式时间内运行，无法修改它以找到最短的哈密顿路径。 (这个逻辑成立吗？)

但是，如果给定一个无向图(所有边都具有非负成本)上的两个节点(比如 A 和 Z)，并且给定至少有一个具有给定节点的哈密顿路径(A和 Z) 作为终点。鉴于这些规范，现在是否可以修改 Dijkstra 算法以找到以 A 和 Z 为端点的最短哈密顿路径？ (多项式时间)

注意:我只关心从两个节点具体找到最短哈密顿路径。例如，如果有一个包含 26 个节点(标记为 A 到 Z)的图，那么通过所有点但从 A 开始到 Z 结束的最短路径是什么。(我不关心找到其他具有不同的哈密顿路径端点，只有 A 和 Z)

附加问题:如果答案是“否”，但有另一种算法可以用来解决这个问题，它是什么算法，它的时间复杂度是多少？

(注意:这个问题有“哈密顿循环”作为标签，即使我正在寻找哈密顿路径，因为我没有足够的代表来制作标签“哈密尔顿路径”。但是，让我们说A和Z恰好有一条边相连，那么最短的哈密顿路径可以通过找到最短的哈密顿环然后去掉A和Z相连的边来找到)

Answer 1

不，这是不可能的。您的简化问题仍然是 NP-hard。减少旅行推销员:

给定一个图 (V, E)，找到访问 V 中的每个 v 恰好一次的最短路径。取一个任意顶点 v in V。将 v 拆分为两个顶点 v_source 和 v_sink。使用您的算法找到从 v_source 到 v_sink 的最短汉密尔顿路径 P。 P 是从 v 开始和结束的最短循环，它访问 V 中的每个 v。由于 P 是一个循环，因此“起始”顶点是无关紧要的。因此，P 也是旅行商问题的解。

减少显然是多项式时间(实际上是常数)，所以你的问题是 NP-hard。