图 - 如何找到最低的定向周期（最低总重量）？ [英] graph - How to find Minimum Directed Cycle (minimum total weight)?

问题描述

下面是一个消费：

  

让G是一个加权有向图有n个顶点和m条边，所有的边缘有积极的权重。有向周期是开始和结束于相同的顶点并且含有至少一个边缘的有向路径。举一个为O（n ^ 3）算法来找到最小的总重量G的定向循环。部分信贷将获得一个O（（N ^ 2）* M）算法。

---

下面是我的算法。

我做了 DFS 。当我找到一个回力每一次，我知道我已经有了一个向圈。

然后，我会暂时沿父阵列（直到我通过在循环中的所有顶点距离）倒退，并计算出总重量。

然后，我比较总重量这个周期与分。 分始终以最低的总重量。在DFS完成后，我们的最低执导周期也发现了。

---

好吧，那么关于时间复杂度。

说实话，我不知道我的算法的时间复杂度。

有关的DFS，遍历需要O（M + N）（如果m是边缘的数目，和n为顶点的数目）。对于每一个顶点，它可能指向回它的一个祖先，从而形成一个循环。当一个周期被发现，它需要O（N）来概括的总重量。

所以我认为，总的时间是O（M + N * N）。但很明显，这是错误的，因为在消费的最佳时间为O（n ^ 3）与正常时间规定为O（M * N ^ 2）。

---

谁能帮我：

1. 是我的算法是否正确？
2. 什么是时间复杂度，如果我的算法是正确的？
3. 有没有针对此问题的任何更好的算法？

解决方案

您可以使用弗洛伊德，沃肖尔算法在这里。

在弗洛伊德算法之间找到最短路径所有对顶点。

该算法是那么很简单，去了所有对（U，V）和发现最小 DIST对（ U，V）+ DIST（V，U） ，因为这对表示从 U 周期至 U 体重 DIST（U，V）+ DIST（V，U）。如果该图还可以自循环（边（U，U）），你还需要单独检查他们，因为这些周期（也只有他们）不由该算法检查。

伪code：

 在图形上运行弗洛伊德沃肖尔
分钟＆lt;  - 无限远
顶点＆LT;  - 没有
对于每对顶点U，V
    如果（DIST（U，V）+ DIST（V，U）其中;分）：
           分钟＆lt;  - 距离（U，V）+ DIST（V，U）
           对＆LT;  - （U，V）
返回路径（U，V）+路径（V，U）
 

路径（U，V）+路径（V，U）实际上是发现从u到v，然后从v到u的路径，这是一个循环。

该算法运行时间为O（n ^ 3），因为弗洛伊德 - 沃肖尔是瓶颈，因为环路发生为O（n ^ 2）的时间。

我觉得在这里正确性是微不足道的，但让我知道如果你不同意我，我会尽力解释它更好的。

Here is an excise:

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.

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.

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.

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.

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

---

Can anyone help me with:

1. Is my algorithm correct?
2. What is the time complexity if my algorithm is correct?
3. Is there any better algorithm for this problem?

解决方案

You can use Floyd-Warshall algorithm here.

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

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.

pseudo code:

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

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屋！