algorithm - 在具有相同顶点和边数的带权无向图中寻找具有最大成本的简单路径的问题是 NP 完全的吗？

Question

您好，再次感谢您阅读本文。

我现在需要知道在具有相同顶点和边数的加权无向图中找到具有最大成本的简单路径的问题是否是 NP 完全问题？

输入图 G = (V,E) 其中 V(顶点)= E(边)

输出:图 G 中最昂贵路径的成本。

您能否提供我可以查看这篇文章的任何引用信息。

非常感谢您的宝贵时间。

此致

亚历克斯。

Answer 1

如果图不一定是连通的，那么最长路径问题的任何实例都可以通过向输入图添加额外的孤立顶点以使节点和边的数量相同来简化为该问题。如果这不是甲状腺情况，并且图必须连通，则输入图必须恰好有一个循环，因为具有 n-1 条边的图是一棵树。如果您使用 DFS 找到这个循环并将其收缩到单个节点，那么您就有了一棵树。在这里计算最长路径很容易；只需考虑所有对边并获得它们之间唯一路径的成本。如果你采用这条路径，然后通过围绕你最初经过收缩节点的循环走动，在原始图中扩展它，我认为你会在多项式时间内获得最长的路径。