在访问所有节点的图中查找最短路径

Question

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

这不是旅行推销员问题：我不需要访问每个顶点一次，也不想回到第一个顶点。

Answer 1

试着看看Dijkstra的算法

其基本思想是过滤遍历所有节点的路由，得到路径最短的路由。

卜实际上这可能不是最佳方式。

Answer 2

这个问题基本上是NP难的，我将给出一个证明（而不是一个适当的简化），这解释了除非P=NP，否则这个问题没有多项式解。

假设这个问题可以在多项式时间内通过某种算法A（G，x，y）

定义以下算法：

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

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

-

复杂性：

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

假设存在这样一个算法，哈密顿路径可以在多项式时间内求解，因为它（哈密顿路径问题）是NP完全的，P=NP。