algorithm - graph - 如何找到最小有向循环(最小总重量)？

Question

这是一个消费税:

Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an O(n^3) algorithm to find a directed cycle in G of minimum total weight. Partial credit will be given for an O((n^2)*m) algorithm.

---

这是我的算法。

我做了一个DFS。每次当我找到一个 back edge 时，我就知道我有一个定向循环。

然后我会暂时沿着父数组倒退(直到我遍历循环中的所有顶点)并计算总权重。

然后我将这个循环的总重量与min进行比较。 min 总是取最小的总权重。 DFS完成后，我们的最小有向环也找到了。

---

好吧，接下来是时间复杂度。

老实说，我不知道我的算法的时间复杂度。

对于 DFS，遍历需要 O(m+n)(如果 m 是边数，n 是顶点数)。对于每个顶点，它可能指向其祖先之一，从而形成一个循环。当找到一个循环时，需要 O(n) 来汇总总权重。

所以我认为总时间是O(m+n*n)。但显然是错误的，因为excise中说最佳时间是O(n^3)，正常时间是O(m*n^2)。

---

谁能帮我:

1. 我的算法正确吗？
2. 如果我的算法正确，时间复杂度是多少？
3. 这个问题有更好的算法吗？

Answer 1

您可以使用 Floyd-Warshall算法在这里。

Floyd-Warshall 算法寻找所有顶点对之间的最短路径。

算法非常简单，遍历所有对 (u,v)，找到最小化 dist(u,v)+dist(v, u)，因为这对表示从 u 到 u 的循环，权重为 dist(u,v)+dist( v,u)。如果图形还允许自循环(边 (u,u))，您还需要单独检查它们，因为算法未检查这些循环(并且只有它们)。

伪代码:

run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
    if (dist(u,v) + dist(v,u) < min):
           min <- dist(u,v) + dist(v,u)
           pair <- (u,v)
return path(u,v) + path(v,u)

path(u,v) + path(v,u)其实就是找到从u到v再从v到u的路径，这是一个循环。

算法运行时间为 O(n^3)，因为 floyd-warshall 是瓶颈，因为循环需要 O(n^2) 时间。

我认为这里的正确性微不足道，但如果您不同意我的观点，请告诉我，我会尽力解释得更好。