그래프에 음수주기가 있는지를 감지하는 가장 빠른 알고리즘

Question

그래프를 표시하려면 행렬 d을 사용합니다. d.(i).(j)은 i과 j 사이의 거리를 의미합니다. v은 그래프의 노드 수를 나타냅니다.

이 그래프에는 음수 사이클이있을 수 있습니다.

부정적인주기가 존재하는지 확인하고 싶습니다.

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 

내 질문

1. 가 올바른 위의 코드는 다음과 같습니다 Floyd-Warshall의 변형에서 다음과 같이 뭔가를 작성했습니다?
2. part 1은 유용합니까?

이 함수를 매우 자주 호출하기 때문에 가능한 한 빨리 만들고 싶습니다. 그래서 내 3) 질문은 다른 알고리즘 (특히 Bellman-Ford)보다 빠를 수 있다면?

Answer 1

코드의 정확성에 대한 첫 번째 질문은 http://codereview.stackexchange.com에 더 적절합니다.

---

어느 Bellman-Ford 또는 Floyd-Warshall이 문제에 적합하다. 성능의 비교는 다음과 같습니다

• Bellman-Ford (위키 백과)
  • 시간 복잡도 : O(|V|*|E|)
  • 공간 복잡도 : O(|V|)
  • The section on "Finding negative cycles" 당신이
• Floyd-Warshall
를 원하는 것입니다 (위키 백과)
• 시간 복잡도 : O(|V|^3)
• 공간 복잡도 : |E| 이후 O(|V|^2)

이 |V|^2에 의해 제한되고, Bellman-Ford은 분명 승자이고 나는 당신이 사용 권합니다 것입니다.

---

부정적인 사이클이없는 그래프 가 예상 일반적인 경우, 당신의 알고리즘의 첫 번째 단계로 신속하게 검사 할 적합 할 수 있습니다 경우 : 그래프는 어떤 부정적인 가장자리를 포함 않습니다를? 그렇지 않다면 물론 그것은 부정적인 사이클을 포함하지 않으며 어떤 부정적인 사이클의 존재를 탐지하기위한 최선의 알고리즘은 O(|E|)입니다.