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

Question

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

上）

O(n.log(n)) 但不是 O(n)

O(n^1.5) 但不是 O(nlogn)

O(n^3) 但不是 O(n^1.5)

O(2n) 但不是 O(n^3)

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

标签： algorithmgraph

Answer 1

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

正如这里提到的，

图必须是非循环的，否则路径可以具有任意大的权重。我们可以通过否定所有边缘权重，然后使用最短路径算法来找到最长路径。不幸的是，如果允许边具有负权重，则 Dijk stra 的算法不起作用。然而，只要不存在负权重循环，Floyd-Warshall 算法确实有效，因此它可用于在无环图中找到最长的权重路径。