負のサイクル

Question

とベルマン・フォードのアルゴリズム私はパスがあるかどうかをテストするために、このメソッドを使用してベルマン・フォードのアルゴリズムを使用して最短経路を見つけようとしている場合このアルゴリズムに起こる？私はDijkstraのアルゴリズムが負のサイクルでは機能しないが、Fordの場合はどうなるのでしょうか？

Answer 1

これは機能しますが、値が最短のパスである場合とそうでない場合があります。実際の最短経路は、実際には負の無限大であり得る。なぜなら、負の円が目的地ノードに到達すると、現在の最短経路よりも短い経路が常に存在するからである。

これは実際にベルマンフォードを使ってマイナスの円を検出する方法です。 after | V |ループでは、（| V | + 1）thはまだ最短経路を更新しますが、グラフにはマイナスの円があります。