给出一个加权无向图有n个顶点，我发现面对的问题 最小重量中连接各顶点在一条线上的路径。 起初，我以为这是寻找最小生成树问题 但这种情况并非如此。如果生成树的，有可能是分支机构 在一个顶点或程度可以大于2。我需要找到一个 即除了结束顶点的所有顶点线性路径有度正好有两个。 开始和结束点可以是任意n个顶点。

Given a weighted undirected graph with n vertices, I face the problem of finding a path of minimum weight that connects each of the vertices in a line. At first, I thought this is the problem of finding the minimum spanning tree but this is not the case. In case of a spanning tree, there may be branches at a vertex or the degree may be greater than two. What I need to find is a linear path i.e all the vertices except the end vertices have degree exactly two. The start and end vertex can be any of the n vertices.

我的是一个贪婪的方法即

Mine was a greedy approach i.e

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors
    mark this neighbor as visited
    add the cost to sum
repeat the procedure above until all the points have been visited.

我将必须做到这一点的所有顶点作为起点。 我不知道该算法是正确的，也是它的复杂度较高。 应该用什么更好的方法这个问题？

I will have to do this for all the vertices as the starting point. I am not sure if this algorithm is correct and also its complexity is high. What should be the better approach to this problem?

推荐答案

这个问题被称为是NP难通过的的汉弥尔顿路径问题 ，因为如果你给所有的边权重为1，问是有重量的最多n的线性路径？那么答案是是precisely如果图中包含一个哈密尔顿路径。这样一来，你是不可能找到一个算法，它的工作原理不是纯蛮力更好，因为除非P = NP不存在多项式时间的解决方案。

This problem is known to be NP-hard by a reduction from the Hamiltonian path problem, since if you give all the edges weight 1 and ask "is there a linear path of weight at most n?" then the answer is "yes" precisely if the graph contains a Hamiltonian path. As a result, you are unlikely to find an algorithm that works better than pure brute force, since unless P = NP there are no polynomial-time solutions.

对不起下雨在您的游行，并希望这有助于！

Sorry to rain in on your parade, and hope this helps!