图-如何找到最小有向循环（最小总权重）？

Question

这是我的算法。

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

然后我将暂时沿着父数组向后（直到我在循环中遍历所有顶点），并计算总权重。

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)