最快的算法,以检测是否有在一个图中的负圆 [英] Fastest algorithm to detect if there is negative circle in a graph
问题描述
我用的矩阵 D
来present图。 D。(我)。(J)
指的的距离我
和Ĵ
; v
表示在图中节点的数目。
I use a matrix d
to present a graph. d.(i).(j)
means the distance between i
and j
; v
denotes the number of nodes in the graph.
有可能存在在此图中的负循环。
It is possible that there is negative circle in this graph.
我想检查是否负圈存在。我已经写了一些东西弗洛伊德 - 沃肖尔的变化如下:
I would like to check if a negative circle exists. I have written something as follows from a variation of Floyd-Warshall:
let dr = Matrix.copy d in
(* part 1 *)
for i = 0 to v - 1 do
dr.(i).(i) <- 0
done;
(* part 2 *)
try
for k = 0 to v - 1 do
for i = 0 to v - 1 do
for j = 0 to v - 1 do
let improvement = dr.(i).(k) + dr.(k).(j) in
if improvement < dr.(i).(j) then (
if (i <> j) then
dr.(i).(j) <- improvement
else if improvement < 0 then
raise BreakLoop )
done
done
done;
false
with
BreakLoop -> true
我的问题是
- 是code以上正确吗?
- 是
第1部分
有用吗?
- Is the code above correct?
- Is the
part 1
useful?
由于我调用该函数很多时候,我真的想让它尽可能快。所以,我的3个)问题是,如果其他算法(尤其是贝尔曼 - 福特
)可以比快?
Because I call this function very often, I really want to make it as fast as possible. So my 3) question is if other algorithms (especially Bellman-Ford
) can be quicker than that?
推荐答案
有关您code是正确的第一个问题是更适合的 HTTP://$c$creview.stackexchange.com
The first question about the correctness of your code is more appropriate for http://codereview.stackexchange.com.
无论贝尔曼 - 福特或的弗洛伊德 - 沃肖尔是适合这个问题。业绩比较如下:
Either of Bellman-Ford or Floyd-Warshall is appropriate for this problem. A comparison of performance follows:
- 贝尔曼 - 福特(维基百科)
- 时间复杂度:
O(| V | * | E |)
- 空间复杂度:
O(| V |)
- 的查找负循环的部分是什么你想
- Bellman-Ford (Wikipedia)
- Time-complexity:
O(|V|*|E|)
- Space-complexity:
O(|V|)
- The section on "Finding negative cycles" is what you want
- 时间复杂度:
O(| V | ^ 3)
- 空间复杂度:
O(| V | ^ 2)
- Time-complexity:
O(|V|^3)
- Space-complexity:
O(|V|^2)
由于
| E |
是界| V | ^ 2
,贝尔曼 - 福特是明显的赢家,是什么,我会建议你使用。Since
|E|
is bounded by|V|^2
, Bellman-Ford is the clear winner and is what I would advise you use.如果图的没有的负循环是预期的正常情况下,它可能是适当的做一个快速检查作为你的算法的第一步:请问图中包含任何负面的边缘?如果没有,那么它当然不包含任何负面的周期,和你有一个
O(| E |)
最好的情况下检测算法任何负面的presence周期。If graphs without negative cycles is the expected normal case, it might be appropriate to do a quick check as the first step of your algorithm: does the graph contain any negative edges? If not, then it of course does not contain any negative cycles, and you have a
O(|E|)
best case algorithm for detecting the presence of any negative cycles.这篇关于最快的算法,以检测是否有在一个图中的负圆的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
- Time-complexity:
- 时间复杂度: