检测图形中是否存在负周期的最快算法 [英] Fastest algorithm to detect if there is negative cycle in a graph

问题描述

我使用矩阵 d 表示图表。 d。（i）。（j）表示 i 和 j之间的距离; v 表示图中的节点数。

此图中可能存在负循环。

我想检查是否存在负循环。我从 Floyd-Warshall 的变体中写了以下内容：

  let dr = Matrix.copy d in 
 
（* part 1 *）
 for i = 0至v-1做
博士（i）。（i）<-0 
完成; 
 
（*第2部分*）
尝试
 for k = 0到v-1做
 for i = 0到v-1做
 j = 0至v-1做
让改善= 
中的（i）。（k）+（k）博士。博士（i）。（j）然后（
如果（i< j））然后
博士（i）。（j）<-改善
如果改善< ; 0然后
提高BreakLoop）
完成
完成
完成； 
错误
和
 BreakLoop->真
  

我的问题是

1. 上面的代码正确吗？


2. 第1部分有用吗？



因为我经常调用此函数，所以我真的想使其尽可能快。所以我的3）问题是，其他算法（尤其是 Bellman-Ford ）是否可以比这更快？

解决方案

关于代码正确性的第一个问题更适合 http://codereview.stackexchange.com 。

---

贝尔曼福特或 Floyd-Warshall 适用于此问题。性能比较如下：

• 贝尔曼·福特（维基百科）
  
  
  
  • 时间复杂度： O（| V | * | E |）
  
  
  • 空间复杂度： O（| V |）
  
  
  • 有关查找负周期的部分是您想要的
  
  


• 弗洛伊德·沃舍尔（维基百科）
  
  
  
  • 时间复杂度： O（| V | ^ 3）
  
  
  • 空间复杂度： O（| V | ^ 2）
  
  

因为 | E | 受限制 | V | ^ 2 ，贝尔曼·福特是最重要的ar赢家，我会建议您使用它。

---

如果图没有的负周期是在预期的正常情况下，作为算法的第一步，可能需要进行快速检查：图形是否包含负边缘？如果不是，那么它当然不包含任何负循环，并且您有一个 O（| E |）最佳情况算法来检测是否存在任何负循环。 / p>

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 cycle in this graph.

I would like to check if a negative cycle 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

My questions are

1. Is the code above correct?
2. Is the part 1 useful?

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?

解决方案

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:

• Bellman-Ford (Wikipedia)
  • Time-complexity: O(|V|*|E|)
  • Space-complexity: O(|V|)
  • The section on "Finding negative cycles" is what you want
• Floyd-Warshall (Wikipedia)
  • Time-complexity: O(|V|^3)
  • Space-complexity: O(|V|^2)

Since |E| is bounded by |V|^2, Bellman-Ford is the clear winner and is what I would advise you use.

---

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