ダイクストラのアルゴリズムはベルマン アルゴリズムよりも効率的ですが、負のエッジにはベルマン フォード アルゴリズムを使用しますが、これらの負のエッジはネットワークで何を表しているのでしょうか? この質問への答えがどこにも見つからず、この質問は私を殺しています。いくつかのアプリケーションが必要なだけで、本当に便利だと感じることができます.
1 に答える
0
Bellman-Ford アルゴリズムは、RIP や RIPv2 などの DVR プロトコルで使用されます。
ウィキから
負の辺の重みはグラフのさまざまなアプリケーションで見られるため、このアルゴリズムの有用性があります[2]。グラフに「負のサイクル」、つまりエッジの合計が負の値になるサイクルが含まれる場合、最も安いパスはありません。これは、どのパスも負のサイクルをもう 1 回歩くことで安くなる可能性があるためです。このような場合、Bellman-Ford アルゴリズムは負のサイクルを検出してその存在を報告できますが、ソースから負のサイクルに到達できる場合、正しい「最短経路」の回答を生成することはできません。
于 2013-10-25T18:18:38.647 に答える