algorithm - 最长的简单路径

Question

所以，我知道在图中寻找最长简单路径的问题是 NP-hard 问题，因为您可以通过将边权重设置为 1 并查看最长简单路径的长度是否等于边的数量。

我的问题是:如果你拿一张图，你会得到什么样的路径，找到最大边权重 m，用 替换每个边权重 w >m - w，然后运行一个标准的最短路径算法？这显然不是最长的简单路径，因为如果是的话，那么 NP = P，我认为类似的东西的证明会有点复杂 =P。

Answer 1

如果你可以用负权重解决最短路径问题，你会找到一条最长路径，两者是等价的，这可以通过将权重设为 -w 而不是 w 来完成

负权重的标准算法是Bellman-Ford算法。但是，如果图中存在一个循环，使得边的总和为负，则该算法将不起作用。在您创建的图表中，所有此类循环的总和权重均为负，因此该算法将不起作用。当然，除非你没有循环，在这种情况下你有一棵树(或一片森林)并且问题可以通过动态规划解决。

如果我们用 m-w 替换 w 的权重，这保证所有权重都是正的，那么可以通过标准算法找到最短路径。如果此图中的最短路径 P 有 k 个边，则长度为 k*m-w(P)，其中 w(P) 是具有原始权重的路径的长度。这条路径不一定是最长的，但是，在所有有 k 条边的路径中，P 是最长的一条。