图 - 如何找到最低向圈(最低总重量)?(graph - How to find Minimum D

2019-06-24 04:44发布

这里是一个消费:

设G为加权有向图有n个顶点和m条边,其中所有边缘具有正权重。 有向周期是开始,并在同一顶点结束,并且含有至少一个边缘的有向路径。 得到为O(n ^ 3)的算法来查找在最小总重量G的定向循环。 部分信用将给出用于O(第(n ^ 2)* M)算法。


这是我的算法。

我做了DFS 。 每次当我找到一个时间back edge ,我知道我有一个定向循环。

然后,我会暂时倒退沿parent array (直到我通过在循环中的所有顶点旅行),并计算出total weights

然后,我比较total weight这个周期与minmin总是需要最小的总重量。 在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:

你可以用弗洛伊德-沃肖尔这里的算法。

弗洛伊德- Warshall算法找出所有顶点之间的最短路径。

该算法则很简单,去了所有对(u,v)并且发现,最小化对dist(u,v)+dist(v,u)因为这对上一周期表示从uu体重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)实际上是到v从u找到的路径,然后从v到u,这是一个循环。

该算法运行时间O(n^3)由于弗洛伊德-沃肖尔是瓶颈,由于环路采用O(n^2)的时间。

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



Answer 2:

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

我想可能重新指向任何始祖这是指N

另外,是ü会如何,当你走出了DFS的标记顶点,你可能会再次从其他顶点来到那里,它的将是另一个循环。 因此,这不是(N + M)DFS了。

  1. 所以乌尔ALGO是不完整
  2. 同样在这里

3.在一个DFS,我认为,顶点应该是看不见的,或检查,并托运u能存储的最小重量为路径开始顶点。 所以,如果一些其他阶段ü找到一个边缘到顶点u不必寻找这个路径了。 这DFS会找到包含第一个顶点最小执导周期。 和它的为O(n ^ 2)(O(N + M)如果u存储图形作为列表)

因此,如果从任何其他顶点做它会是为O(n ^ 3)(O(N *(N + M))

对不起,我的英语水平,我不擅长术语



Answer 3:

是我的算法是否正确?

号让我举一个反例。 想象一下,你从开始DFS u ,有两条路径p1p2uv和1路p3v回到up1是短于p2

假设你通过采取启动p2路径v ,并步行回u由路径p3 。 一个周期发现,但显然它不是最小的。 然后你继续探索u通过采取p1路径,但由于v被充分发掘,在DFS没有找到的最小周期结束。



Answer 4:

我做了类似这样的事情,但我没有使用DFS(这是需要我的算法正常工作),因此我意识到,我的算法是的指数复杂任何访问阵列。

因为,你发现所有的周期,不可能找到所有的周期,在不到指数的时间,因为可以有2 ^(E-V + 1)周期。



文章来源: graph - How to find Minimum Directed Cycle (minimum total weight)?