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

Question

我有一个带权无向图 G，其中有 n 个顶点。其中两个顶点是 X 和 Y。
我需要找到从 X 开始、以 Y 结束并经过 G 中所有顶点（以任意顺序）的最短路径。
我该怎么做呢？
这不是旅行商问题：我不需要只访问每个顶点一次，也不想回到第一个顶点。

- Myah

---

在这种情况下会发生什么：u->v，v->u。这会花费我们2*w吗？我认为应该是的（我只是想确认一下），因为如果不是的话，你就必须找到最小生成树（MST）。 - farzadshbfn

这个问题对我来说似乎是NP难的。任何想法吗？ - displayName

是的，这是NP-难问题，“松弛”并不能使它变得更容易。如果能够找到连接所有节点的给定两个点之间的最短路径，那么通过检查所有节点对X,Y（有多项式数量的节点对）就很容易找到一个图是否具有哈密顿回路。 - amit

@amit：这正是我所想的。 - displayName

Answer 1

这个问题基本上是NP难问题，我将提供一个证明的草图（而不是正式的归约），它解释了除非P = NP，否则没有多项式解决方案。

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

定义以下算法：

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

该算法解决哈密顿路径问题。

-> 如果存在一条通过所有节点且长度恰好为|V|的路径，它没有重复使用任何顶点，并且找到的路径是哈密顿路径。

<- 如果存在哈密顿路径v1->v2->...->vn，则调用A(G,v1,vn)时，您将找到最短可能的路径，其长度最多为|V|-1(因为它需要经过所有顶点)，并且算法将返回true。

复杂度:

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

因此，假设存在这样的算法，哈密顿路径问题可以在多项式时间内解决，而且由于它（哈密顿路径问题）是NP-Complete，P=NP。

- amit

Answer 2

尝试查看迪杰斯特拉算法

基本思想是过滤遍历所有节点的路线，并获取最短路径的路线。

但实际上，这可能不是最优的方法。

- Igor Karbachinsky

---

Dijkstra算法不能解决我的问题。使用Dijkstra算法可以找出两个顶点之间的最佳路径，但不一定经过所有顶点。 - Myah