algorithm - 在图中找到任意大权重的路径

Question

给定一个带 n 个顶点的带权有向图，其中边权重为整数(正、零或负)，判断是否存在任意大权重的路径可以及时执行 -

O(n)

O(n.log(n)) but not O(n)

O(n^1.5) but not O(nlogn)

O(n^3) but not O(n^1.5)

O(2n) but not O(n^3)

我不明白要使用什么算法，因为寻找最长路径是一个 NP 难题。虽然，给出的答案是 O(n^3)

Answer 1

简而言之，您必须对权重取反，然后运行 ​​Floyd-Warshall 算法。它需要 O(n^3)。

如前所述here ,

The graphs must be acyclic, otherwise paths can have arbitrarily large weights. We can find longest paths just by negating all of the edge weights, and then using a shortest path algorithm. Unfortunately, Dijk stra’s algorithm does not work if edges are allowed to have negative weights. However, the Floyd-Warshall algorithm does work, as long as there are no negative weight cycles, and so it can be used to find longest weight paths in acyclic graphs.