图表-如何找到最小定向循环（最小总重量）？

Question

这是消费税：

令G为具有n个顶点和m个边的加权有向图，其中所有边的权重为正。有向循环是有向路径，该路径在相同的顶点处开始和结束，并包含至少一条边。给出一个O（n ^
3）算法，以找到最小总重量的G中的有向循环。对于O（（n ^ 2）* m）算法，将给予部分功劳。

这是我的算法。

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

然后，我将暂时沿前进parent array（直到我遍历循环中的所有顶点）并计算total weights。

然后，我total weight将此循环的与进行比较min。min始终采用最小的总重量。DFS完成后，还会找到我们的最小定向周期。

好吧，那么关于时间的复杂性。

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

对于DFS，遍历采用O（m +
n）（如果m是边的数量，而n是顶点的数量）。对于每个顶点，它可能指向其祖先之一，因此形成一个循环。找到一个周期后，需要O（n）来汇总总权重。

所以我认为总时间为O（m + n * n）。但是很显然这是错误的，正如消费税中所述，最佳时间是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)时间。

我认为这里的正确性是微不足道的，但是如果您不同意我的话，请告诉我，我会尽力向您解释。