「ソースから負のエッジ サイクルに到達できる場合、アルゴリズムは false を返します」と言われています。
この「ソースから到達可能」とは何を示していますか?
次の画像を見てください。
ソースから到達可能な負のエッジ サイクルが存在する場合、このアルゴリズムが false を返す例を教えてください。
注：私はアルゴリズムが初めてです。
質問する
1808 次
2 に答える
1
つまり、総重みが負のサイクルが存在する場合、そのサイクルを繰り返したどるとパスの重みが「減少」するため、アルゴリズムは答えを出すことができません。あなたが示しているグラフには（検査による）負の重みサイクルは見られないので、あなたの場合、述べられた制限は問題ではないはずです。
編集：「ソースから到達可能」とは、負の重みサイクルが、開始ノードまたはソースノードから到達可能である場合にのみ問題になることを意味します。つまり、指定されたソースから負の重みサイクルのノードへのパスが存在します。ベルマンフォードは、識別されたノードからそのノードから到達可能なすべてのノードへの最短経路を見つけます。それは理にかなっていますか？
于 2012-10-23T19:08:23.127 に答える
1
このアルゴリズムを使用して最短経路を見つける場合、負のサイクルの存在が問題となり、アルゴリズムが正しい答えを見つけられなくなります。ただし、負のサイクルが検出されると終了するため、ベルマンフォード アルゴリズムは、ネットワーク フロー解析におけるサイクル キャンセリング テクニックなど、これが対象となるアプリケーションに使用できます。
このリンクを参照してください:- http://evlm.stuba.sk/~partner2/DBfiles/Optimization/Dynamic%20optimization/Optimization_EN_Ford-Belman_algorithm.pdf
于 2012-10-23T19:11:19.487 に答える