这是消费税：
令G为具有n个顶点和m个边的加权有向图，其中所有边的权重为正。有向循环是有向路径，该路径在相同的顶点处开始和结束，并包含至少一条边。给出一个O（n ^ 3）算法，以找到最小总重量的G中的有向循环。对于O（（n ^ 2）* m）算法，将给予部分功劳。
这是我的算法。
我做一个DFS。每当我找到一个时back edge，我就知道我有一个定向循环。
DFS
back edge
然后，我将暂时沿前进parent array（直到我遍历循环中的所有顶点）并计算total weights。
parent array
total weights
然后，我total weight将此循环的与进行比较min。min始终采用最小的总重量。DFS完成后，还会找到我们的最小定向周期。
total weight
min
好吧，那么关于时间的复杂性。
老实说，我不知道算法的时间复杂度。
对于DFS，遍历采用O（m + n）（如果m是边的数量，而n是顶点的数量）。对于每个顶点，它可能指向其祖先之一，因此形成一个循环。找到一个周期后，需要O（n）来汇总总权重。
所以我认为总时间为O（m + n * n）。但是很显然这是错误的，正如消费税中所述，最佳时间是O（n ^ 3），而正常时间是O（m * n ^ 2）。
谁能帮助我：
您可以在此处使用Floyd- Warshall算法。
Floyd-Warshall算法可以找到 所有 顶点 对 之间的最短路径。
该算法则很简单，去了所有对(u,v)，并 找到一对最小化dist(u,v)+dist(v,u)，因为这对上一周期表示从u到u与重量dist(u,v)+dist(v,u)。如果该图还允许自环（边(u,u)），则您还需要单独检查它们，因为算法没有检查这些循环（并且只有它们）。
(u,v)
dist(u,v)+dist(v,u)
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的路径，这是一个循环。
path(u,v) + path(v,u)
算法运行时间为O(n^3)，因为floyd-warshall是瓶颈，因为循环需要O(n^2)时间。
O(n^3)
O(n^2)
我认为这里的正确性是微不足道的，但是如果您不同意我的话，请告诉我，我会尽力向您解释。
