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

Question

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

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

不需要访问所有节点或边缘。

方法和序言资源建议会很好。

Answer 1

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

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

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

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