您好，再次感谢您阅读本文。
我现在需要知道在具有相同顶点和边数的带权无向图中找到具有最大成本的简单路径的问题是否是NP完全问题？
输入:图 G = (V,E)，其中 V(顶点)= E(边)
输出:图 G 中最昂贵路径的成本。
您能否提供一篇文章的引用资料，我可以在其中进行审阅。
非常感谢您抽出时间。
真诚的，
亚历克斯。
最佳答案
如果图不一定是连通的，那么最长路径问题的任何实例都可以通过向输入图添加额外的孤立顶点以使节点和边的数量相同来简化为该问题。如果这不是甲状腺情况，并且图必须是连接的，那么输入图必须恰好有一个循环，因为具有 n-1 条边的图是一棵树。如果你用 DFS 找到这个循环并将其收缩到单个节点，那么你就得到了一棵树。在这里很容易进行最长路径计算；只需考虑所有边对并获取它们之间唯一路径的成本。如果你采用这条路径，然后通过绕着你最初经过收缩节点的循环在原始图中扩展它，我认为你会得到多项式时间内最长的路径。
关于algorithm - 在具有相同顶点和边数的加权无向图中找到具有最大成本的简单路径问题是NP完全问题吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4558077/