使用 Floyd-Warshall 算法求解最小权重环

Question

"让G成为一个没有负环的有向加权图。设计一种算法，在O（|V|^3）的时间复杂度内寻找G中的最小权重循环。"

"上面是我在课程作业中研究的一个问题。当我第一次阅读它时，我立即想到 Floyd-Warshall 算法可以解决这个问题 - 主要是因为 F-W 运行时间为 O（|V|^3），并且适用于没有负环的正权和负权图。然而，我很快就想起了 F-W 的主要目的是寻找图的最短路径，而不是最小权重循环。"

"我对这个问题的思路正确吗？是否可能修改 Floyd-Warshall 算法来找到图中的最小权重循环？"

- user1696230

---

是的，你走在正确的道路上了。包含顶点v的最小权重环由以_____开头的最小权重_____，后跟一个_____组成。请填空 :) - j_random_hacker

我不知道上面的空白应该是什么，但一个循环是从一个顶点到其自身的（非平凡）路径。你只需要调整FW的初始设置以获得你想要的结果。 - G. Bach

@G.Bach 我认为Hacker的意思是，如果你已经解决了所有对最短路径问题，那么你可以在O(n^3)的时间内构造出最小循环。但是，如果我们想要找到一个没有重复节点的简单循环，则会更加困难。 - Niklas B.

@NiklasB.：我不理解你关于简单环的观点——如果没有负权重环，那么任何两个顶点之间的最短路径必定是简单的（除非它涉及0权重环，但在这种情况下，可以删除它们以得到无环的最短路径，FW算法会找到）。 - j_random_hacker

@NiklasB.：思考一下，FW算法从仅包含0wc-free路径开始，并且仅通过连接现有路径来构建路径。如果将一个0wc-free路径u->x与一个0wc-free路径x->v连接起来产生一个包含0wc的路径u->v，则该循环包含x，并且先前最优路径u->v上必须存在一个顶点y也在该循环中。但是，那么u->y->v就是一条具有与u->x->v相同总距离的0wc-free路径，这意味着u->x->v在第一次选择时永远不会被选中，因为我们仅在新构建的路径严格更短时才更新(u，v)的解决方案。 - j_random_hacker

Answer 1

我认为你接近正解了。一旦你以O(|V|^3)的时间复杂度完成FW（Floyd-Warshall）循环，你就得到了每对顶点之间最短路径的权重，我们称其为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的最短路径，这可以用各种方式来完成。

- llaki