graph-theory - 具有已知起始节点并访问所有节点而不返回起始节点的完整加权无向图中的最短路径

Question

我有一个完整的位置(节点)无向图，其中每条边代表其连接节点之间的距离，我想找到从起始节点开始的最短路径，而不指定结束节点，因此基本上它可以在任何其他节点结束然后是第一个。

我查看了 TSP 问题和最短的哈密顿路径，但找不到对我的问题的确切响应。

那么这个问题究竟叫什么，或者它是最短路径问题的什么变体？

这是我正在寻找的一个例子。让我们有一个完整的加权图如下:

每条边代表两个位置之间的距离，例如边AB=5，AC=11......

我的目标是从节点 A 开始，找到覆盖所有节点的最短路径(最短可能路径)，终点可以是除 A 之外的任何一个。例如，这条以 E 结束的路径:

Answer 1

这是 The Traveling Salesman Path Problem 特殊情况的轻微变化.在旅行商路径问题中，您将获得一个无向图、一个边上的成本函数和两个顶点 s和 t .问题是要找一个Hamiltonian Path (即，只访问每个顶点一次的路径)来自 s至 t .

您的问题是输入图是 clique 的特殊情况和目标顶点 t是一个额外的虚拟顶点，通过 0 成本边连接到所有其他顶点。显然，图的旅行推销员路径问题的解决方案(带有额外的虚拟顶点 t)会导致您的问题的解决方案，通过简单地忽略到达目的地 t 的最后一个额外步骤而获得的解决方案。 .

不幸的是，就像著名的Traveling Salesman Problem , 旅行商路径问题不仅是 NP-hard 问题，而且是 NP-hard 在任何常数因子内逼近的问题。但是，由于您的成本代表距离，也许您可​​以假设成本函数满足 The Triangle Inequality ?

如果代价函数满足三角不等式，则存在最近的1.5-approximation algorithm .如果这个最近的算法是一个矫枉过正的算法，你可以实现两个更简单的算法之一，这些算法在 lecture notes 中有很好的描述。由来自 CMU 的 Ryan O’Donnell 教授编写，并满足于 2 近似值或 5/3 近似值。