给定一个有 n 个顶点的带权无向图，我面临寻找的问题 连接直线中每个顶点的最小权重路径。 一开始我以为这是求最小生成树的问题 但这种情况并非如此。在生成树的情况下，可能有分支 在一个顶点或度数可能大于二。我需要找到的是 线性路径，即除末端顶点外的所有顶点的度数正好为二。 起始和结束顶点可以是n个顶点中的任意一个。
我的方法是贪婪的，即
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.
我必须以所有顶点为起点执行此操作。 我不确定这个算法是否正确，而且它的复杂度很高。 解决这个问题的更好方法应该是什么？
最佳答案
通过从 Hamiltonian path problem 归约，这个问题被认为是 NP-hard ，因为如果你给所有的边赋予权重 1 并问“是否存在权重最多为 n 的线性路径？”那么如果图形包含哈密顿路径，则答案恰恰是"is"。因此，您不太可能找到比纯蛮力效果更好的算法，因为除非 P = NP，否则不存在多项式时间解。
很抱歉打扰您的游行，希望这对您有所帮助!
关于在图中找到最小权重的线性路径的算法，该路径恰好连接所有顶点一次，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9092741/