图 - 如何找到最小有向循环(最小总重量)? [英] graph - How to find Minimum Directed Cycle (minimum total weight)?

问题描述

这是一个消费税:

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

Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an O(n^3) algorithm to find a directed cycle in G of minimum total weight. Partial credit will be given for an O((n^2)*m) algorithm.

<小时>

这是我的算法.

---

Here is my algorithm.

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

I do a DFS. Each time when I find a back edge, I know I've got a directed cycle.

然后我会暂时沿着父数组向后走(直到我遍历循环中的所有顶点)并计算总权重.

Then I will temporarily go backwards along the parent array (until I travel through all vertices in the cycle) and calculate the total weights.

然后我将这个循环的总重量与min进行比较.min 总是采用最小的总权重.DFS 完成后，我们的最小有向循环也被找到了.

Then I compare the total weight of this cycle with min. min always takes the minimum total weights. After the DFS finishes, our minimum directed cycle is also found.

好的，那么关于时间复杂度.

Ok, then about the time complexity.

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

To be honest, I don't know the time complexity of my algorithm.

对于DFS，遍历需要O(m+n)(如果m是边数，n是顶点数).对于每个顶点，它可能会指向它的一个祖先，从而形成一个循环.当找到一个循环时，需要 O(n) 来总结总权重.

For DFS, the traversal takes O(m+n) (if m is the number of edges, and n is the number of vertices). For each vertex, it might point back to one of its ancestors and thus forms a cycle. When a cycle is found, it takes O(n) to summarise the total weights.

所以我认为总时间是 O(m+n*n).但显然这是错误的，如消费税中所述，最佳时间为 O(n^3)，正常时间为 O(m*n^2).

So I think the total time is O(m+n*n). But obviously it is wrong, as stated in the excise the optimal time is O(n^3) and the normal time is O(m*n^2).

谁能帮我:

1. 我的算法正确吗?
2. 如果我的算法正确，时间复杂度是多少?
3. 有没有更好的算法来解决这个问题?

推荐答案

您可以使用 Floyd-Warshall 算法在这里.

You can use Floyd-Warshall algorithm here.

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

The Floyd-Warshall algorithm finds shortest path between all pairs of vertices.

算法非常简单，遍历所有对(u,v)，并找到最小化dist(u,v)+dist(v,u)，因为这对表示在从 u 到 u 的循环上，权重 dist(u,v)+dist(v,u).如果图形还允许自循环(边 (u,u)) ，您还需要单独检查它们，因为算法没有检查这些循环(并且只有它们).

The algorithm is then very simple, go over all pairs (u,v), and find the pair that minimized dist(u,v)+dist(v,u), since this pair indicates on a cycle from u to u with weight dist(u,v)+dist(v,u). If the graph also allows self-loops (an edge (u,u)) , you will also need to check them alone, because those cycles (and only them) were not checked by the algorithm.

伪代码:

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) is actually the path found from u to v and then from v to u, which is a cycle.

算法运行时间是O(n^3)，因为floyd-warshall 是瓶颈，因为循环需要O(n^2) 时间.

The algorithm run time is O(n^3), since floyd-warshall is the bottle neck, since the loop takes O(n^2) time.

我认为这里的正确性是微不足道的，但如果您不同意我的观点，请告诉我，我会尽力解释得更好.

I think correctness in here is trivial, but let me know if you disagree with me and I'll try to explain it better.

这篇关于图 - 如何找到最小有向循环(最小总重量)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！