如何在无向加权图中找到最长（最重）的轨迹？

Question

我有一张美国空间地图，用权重（距离）连接城市。我想找到这张地图中最长（权重最大）的路径。

• 每条边被访问 0 或 1 次
• 每个节点可以被访问 [0, inf) 次。

不要求所有节点或边都需要被访问。

方法和序言资源建议就可以了。

Answer 1

我不知道我是否正确，但你可以尝试以下方法：

1. 您可以检查该图是否是欧拉图。如果是这样，你的问题是找到欧拉电路，这可以在多项式时间内完成。

2. 否则你就会遇到问题，因为如果我没记错的话，你必须找到最大（可能是诱导的）欧拉子图，这是 NP 难的。

当然，一切都假设所有权重都是非负的。