“让 G 是一个没有负循环的有向加权图。设计一种算法来找到 G 中以 O(|V|^3) 的时间复杂度运行的最小权重循环。”
以上是我在课程作业中一直在研究的一个问题。当我第一次阅读它时，我立即认为 Floyd-Warshall 算法可以解决这个问题——主要是因为 FW 运行时间为 O(|V|^3)，它适用于没有负循环的正负加权图。但是，我很快就记起 FW 旨在找到图的最短路径，而不是最小权重循环。
我在这个问题上是否正确？是否可以修改 Floyd-Warshall 算法以在图中找到最小权重循环？
我认为你很接近。一旦你在 O(|V|^3) 中进行 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 的最短路径，这可以通过多种方式完成。