6

マトリックスを使用しdてグラフを表示します。d.(i).(j)と の間の距離を意味しiますj。vグラフ内のノード数を示します。

このグラフには負のサイクルがある可能性があります。

負のサイクルが存在するかどうかを確認したいと思います。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

私の質問は

  1. 上記のコードは正しいですか？
  2. part 1便利ですか？

私はこの関数を頻繁に呼び出すので、できる限り高速にしたいと考えています。だから私の3）質問は、他のアルゴリズム（特にBellman-Ford）がそれよりも速くなるかどうかです。

4

2 に答える 2

4

コードの正確性に関する最初の質問は、http://codereview.stackexchange.comに適しています。

この問題には、 Bellman-FordまたはFloyd-Warshallのいずれかが適しています。パフォーマンスの比較は次のとおりです。

|E|は に制限されているため|V|^2、ベルマンフォードが明らかに勝者であり、これを使用することをお勧めします。

負のサイクルのないグラフが予想される通常のケースである場合、アルゴリズムの最初のステップとして、グラフに負のエッジが含まれているかどうかを簡単に確認することが適切な場合があります。そうでない場合は、もちろん負のサイクルは含まれておらず、負のサイクルO(|E|)の存在を検出するための最良のケースのアルゴリズムがあります。

于 2013-06-03T22:17:35.320 に答える