这里是一个消费:
设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)。
谁能帮我用:
- 是我的算法是否正确?
- 什么是时间复杂度,如果我的算法是正确的?
- 是否有此问题的任何更好的算法?
你可以用弗洛伊德-沃肖尔这里的算法。
弗洛伊德- 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)
实际上是到v从u找到的路径,然后从v到u,这是一个循环。
该算法运行时间O(n^3)
由于弗洛伊德-沃肖尔是瓶颈,由于环路采用O(n^2)
的时间。
我觉得正确性这里是微不足道的,但让我知道,如果你不同意我,我会尽力解释它更好。
“对于每一个顶点,它可能重新指向它的一个祖先,从而形成一个循环”
我想可能重新指向任何始祖这是指N
另外,是ü会如何,当你走出了DFS的标记顶点,你可能会再次从其他顶点来到那里,它的将是另一个循环。 因此,这不是(N + M)DFS了。
- 所以乌尔ALGO是不完整
- 同样在这里
3.在一个DFS,我认为,顶点应该是看不见的,或检查,并托运u能存储的最小重量为路径开始顶点。 所以,如果一些其他阶段ü找到一个边缘到顶点u不必寻找这个路径了。 这DFS会找到包含第一个顶点最小执导周期。 和它的为O(n ^ 2)(O(N + M)如果u存储图形作为列表)
因此,如果从任何其他顶点做它会是为O(n ^ 3)(O(N *(N + M))
对不起,我的英语水平,我不擅长术语
是我的算法是否正确?
号让我举一个反例。 想象一下,你从开始DFS u
,有两条路径p1
和p2
从u
到v
和1路p3
从v
回到u
, p1
是短于p2
。
假设你通过采取启动p2
路径v
,并步行回u
由路径p3
。 一个周期发现,但显然它不是最小的。 然后你继续探索u
通过采取p1
路径,但由于v
被充分发掘,在DFS没有找到的最小周期结束。
我做了类似这样的事情,但我没有使用DFS(这是需要我的算法正常工作),因此我意识到,我的算法是的指数复杂任何访问阵列。
因为,你发现所有的周期,不可能找到所有的周期,在不到指数的时间,因为可以有2 ^(E-V + 1)周期。