基于Floyd-Warshall算法的最小权环

Question

设G是一个无负圈的有向加权图，设计了一种算法，以求G中的最小权圈，其时间复杂度为O({x}V}^3)。

以上是我一直在努力的问题，作为我的课程工作的一部分。当我第一次读到它的时候，我立刻想到Floyd算法可以解决这个问题--主要是因为for运行在O({x}V}^3)的时间里，并且它同时适用于没有负圈的正负加权图。然而，我很快就记得F被设计用来寻找图的最短路径，而不是最小权圈。

我在这个问题上走在正确的轨道上吗？是否有可能修改弗洛伊德-沃尔算法，以求图中的最小权循环？

Answer 1

我觉得你们关系很好。一旦你在O中做了FW循环，你就有了每个顶点之间最短路径的权重，让我们称之为D(i，j)。现在，我们主要问题的解决方案如下:顶点的蛮力，它将在一个循环中，比如X，也就是Y上的蛮力，它将是循环中的最后一个顶点，在X本身之前。该循环的重量明显为D(X，Y) + W(Y，X)。然后你只需选择一个值最小的。这显然是一个正确的答案，因为：(1) D(X，Y)+D(Y，X)的所有值都代表某些(可能是非简单的)循环的权值：(2)如果最优循环是a->.>b->a，那么当X=a，Y=b时，我们考虑它；

要重建答案，首先你需要跟踪哪个X，Y给了我们最优的结果。一旦我们得到了这个X和Y，剩下的唯一的事情就是找到从X到Y的最短路径，这可以用各种方法来完成。