10

这是一个消费税：

令 G 为具有 n 个顶点和 m 个边的加权有向图，其中所有边的权重为正。有向环是在同一顶点开始和结束并包含至少一条边的有向路径。给出一个 O(n^3) 算法，在 G 中找到一个总权重最小的有向循环。O((n^2)*m) 算法将获得部分学分。

这是我的算法。

我做一个DFS。每次当我找到 a 时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. 有没有更好的算法来解决这个问题？
4

4 回答 4

25

您可以在此处使用Floyd-Warshall算法。

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

该算法非常简单，遍历所有对(u,v)，并找到最小化的对dist(u,v)+dist(v,u)，因为这对表示在从u到u和 weight的循环上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)时间。

我认为这里的正确性是微不足道的，但是如果您不同意我的观点，请告诉我，我会尝试更好地解释它。

于 2012-05-05T06:52:52.620 回答
5

我的算法正确吗？

不，让我举一个反例。想象一下，您从 开始 DFS u，有两条路径from top1和1 条路径from back to ，比.p2uvp3vup1p2

假设您从p2路径开始v，然后走回u路径p3。发现了一个周期，但显然不是最少的。然后你继续u走p1路径探索，但由于v完全探索，DFS结束时没有找到最小循环。

于 2012-10-20T10:27:09.587 回答
2

“对于每个顶点，它可能指向它的一个祖先，从而形成一个循环”

我认为它可能指向它的任何祖先，这意味着 N

另外，当你从它的dfs出来时，你将如何标记顶点，你可能会从其他顶点再次来到那里，这将是另一个循环。所以这不再是 (n+m) dfs。

  1. 所以你的算法是不完整的
  2. 同样在这里

3.在一个dfs中，我认为顶点应该是看不见的，或者是检查的，并且对于检查，你可以存储到起始顶点的路径的最小权重。因此，如果在其他阶段您找到了该顶点的边，您就不必再搜索这条路径了。此 dfs 将找到包含第一个顶点的最小有向循环。它是 O(n^2) (O(n+m) 如果你将图形存储为列表)

因此，如果从任何其他顶点执行此操作，它将是 O(n^3) (O(n*(n+m))

对不起，我的英语，我不擅长术语

于 2012-05-05T04:13:07.930 回答
0

我做了类似的事情，但我没有为 dfs 使用任何访问过的数组（这是我的算法正常工作所必需的），因此我意识到我的算法具有指数复杂性。

由于您要找到所有周期，因此不可能在小于指数的时间内找到所有周期，因为可能有 2^(e-v+1) 个周期。

于 2019-01-26T09:12:19.450 回答