algorithm - 在访问所有节点的图中找到最短路径

Question

我有一个带n 个顶点的加权无向图G。其中两个顶点是 X 和 Y。
我需要找到从 X 开始，到 Y 结束并通过 G 的所有顶点(以任何顺序)的最短路径。
我该怎么做？

这不是旅行商问题:我不需要只访问每个顶点一次，也不想返回到第一个顶点。

Answer 1

这个问题基本上是 NP-Hard，我将给出一个证明的草图(而不是适当的归约)，它解释了除非 P = NP , 这个问题没有多项式解。

假设这个问题可以在多项式时间 O(P(n)) 中通过某种算法 A(G,x,y) 解决

>

定义以下算法:

HamiltonianPath(G):
  for each pair (x,y):
      if A(G(x,y) == |V| - 1):
          return true
  return false

这个算法解决了Hamiltonian Path Problem .

-> If there is a path between some pair x,y that goes through all nodes and its length is exactly |V|, it means it did not use any vertex twice, and the path found is Hamiltonian.

<- If there is a Hamiltonian Path v1->v2->...->vn, then when invoking A(G,v1,vn), you will find the shortest possible path, which its length is at most |V|-1 (and it cannot be less because it needs to go through all vertices), and the algorithm will yield true.

复杂度:

算法的复杂度为O(n^2 * P(n))，为多项式时间。

因此，假设存在这样的算法，哈密顿路径可以在多项式时间内求解，因为它(哈密顿路径问题)是 NP-Complete , P=NP.