已知起始节点且访问所有节点而不返回起始节点的完全带权无向图中的最短路径
Shortest path in a complete weighted undirected graph with a known start node and visiting all nodes without returning to start node
我有一个完整的位置（节点）无向图，其中每条边代表其连接节点之间的距离，我想找到从起始节点开始的最短路径而不指定结束节点所以基本上它可以在第一个节点以外的任何节点结束。
我查看了 TSP 问题和最短哈密顿路径，但找不到对我的问题的确切响应。
那么这个问题到底叫什么或者它是最短路径问题的什么变体？
这是我正在寻找的示例。让我们有一个完整的加权图如下：
每条边代表两个位置之间的距离，例如边AB=5，AC=11......
我的目标是从节点A开始，找到覆盖所有节点的最短路径（最短可能路径），终点可以是A以外的任何一个。例如这条以E结束的路径：
这是 The Traveling Salesman Path Problem. In The Traveling Salesman Path Problem, you're given an undirected graph, a cost function on the edges, and two vertices s and t. The problem is to find a Hamiltonian Path 的特例（即访问每个顶点恰好一次的路径）从 s 到 t 的细微变化。
你的问题是输入图是 clique 而目标顶点 t 是一个额外的虚拟顶点，通过 0 成本边连接到所有其他顶点的特殊情况。显然，图的旅行商路径问题的解决方案（带有额外的虚拟顶点 t）可以引出解决问题的方法，只需忽略到达目的地 t 的最后一步即可获得。
不幸的是，就像著名的Traveling Salesman Problem, The Traveling Salesman Path Problem is not only NP-hard, but also NP-hard to approximate to within any constant factor. However, since your costs represent distances, maybe you could assume that the cost function satisfies The Triangle Inequality?
如果成本函数满足三角不等式，则存在 CMU 的 Ryan O'Donnell 教授最近 1.5-approximation algorithm. If this recent algorithm is an overkill, you can implement one of two simpler algorithms that are nicely described in lecture notes 提出的 2 近似或 5/3 近似。
我有一个完整的位置（节点）无向图，其中每条边代表其连接节点之间的距离，我想找到从起始节点开始的最短路径而不指定结束节点所以基本上它可以在第一个节点以外的任何节点结束。
我查看了 TSP 问题和最短哈密顿路径，但找不到对我的问题的确切响应。
那么这个问题到底叫什么或者它是最短路径问题的什么变体？
这是我正在寻找的示例。让我们有一个完整的加权图如下：
每条边代表两个位置之间的距离，例如边AB=5，AC=11......
我的目标是从节点A开始，找到覆盖所有节点的最短路径（最短可能路径），终点可以是A以外的任何一个。例如这条以E结束的路径：
这是 The Traveling Salesman Path Problem. In The Traveling Salesman Path Problem, you're given an undirected graph, a cost function on the edges, and two vertices s and t. The problem is to find a Hamiltonian Path 的特例（即访问每个顶点恰好一次的路径）从 s 到 t 的细微变化。
你的问题是输入图是 clique 而目标顶点 t 是一个额外的虚拟顶点，通过 0 成本边连接到所有其他顶点的特殊情况。显然，图的旅行商路径问题的解决方案（带有额外的虚拟顶点 t）可以引出解决问题的方法，只需忽略到达目的地 t 的最后一步即可获得。
不幸的是，就像著名的Traveling Salesman Problem, The Traveling Salesman Path Problem is not only NP-hard, but also NP-hard to approximate to within any constant factor. However, since your costs represent distances, maybe you could assume that the cost function satisfies The Triangle Inequality?
如果成本函数满足三角不等式，则存在 CMU 的 Ryan O'Donnell 教授最近 1.5-approximation algorithm. If this recent algorithm is an overkill, you can implement one of two simpler algorithms that are nicely described in lecture notes 提出的 2 近似或 5/3 近似。