我有一个有向图 G = (V, E)，其中边具有权重。有些边可能有负权重，但G不包含任何负环。
我有一组新边 S，如果将其添加到 G 中，将导致负循环。我想确定这些边中的哪一个在添加到 G 时会导致负循环。我怎么能这样做？
最佳答案
我认为您可以使用增量调试算法来解决这个问题。这最初是为识别导致程序崩溃的最小测试用例或最小更改集而设计的，但它在这里也应该适用。
在增量调试算法中，您从一些有效的配置开始，并进行一组更改 C，其中将 C 应用于基线配置会导致失败。如果您假设 C 服从特定属性，那么您可以仅进行 O(|C|2) 次测试，确定将导致失败的最小更改集。所需的性质如下:如果 S 是一组导致失败的更改，并且 S ⊆ S'，则 S' 也会导致失败。
在您的情况下，基线集是原始图形，您的更改集是您添加到图形中的边集。如果你添加了一组导致负循环出现的边，那么添加任何包含这些边的集合也会导致循环出现。因此，如果你有一个包含 m 个节点、n 条边的图，并且你有 z 个候选边，你可以在 Bellman-Ford 的 O(z2) 次迭代中(运行时 O((m + z) n)) 确定将导致负循环出现的最小边集。运行时间将为 O(z2(m + z)n)，这对于小 z 来说还算不错。
有关该算法的详细信息可以在 the original paper 中找到或 this set of lecture slides .
希望这对您有所帮助!
关于algorithm - 确定哪一组边会导致负循环？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23428590/