图表 - 如何查找最小定向循环(最小总重量)？

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)时间.

我认为这里的正确性是微不足道的,但如果你不同意我,请告诉我,我会试着更好地解释它.

Answer 2

我的算法正确吗？

不，让我举一个反例。想象一下，您从 开始 DFS u，有两条路径p1，p2从u到v和p3从v返回到的路径有 1 条u，p1比p2.

假设您从p2前往的路径开始v，然后u通过路径返回p3。找到了一个周期，但显然不是最小值。然后你u通过走p1路径继续探索，但由于v已经完全探索，DFS 没有找到最小循环就结束了。