頂点 z から始まるベルマンフォード アルゴリズムを実行する必要がある宿題をやっています。「各パスで、図と同じ順序でエッジを緩和し、各パスの後に d と pi の値を表示する」ように求めています。私が理解していることから、このアルゴリズムは BFS のようにグラフをトラバースすると考えました。これは、使用してほしい図から理解できるので、同じパスがどのように機能するかわかりません。誰かが開始方法を指摘して正しい方向に向けることができれば、非常に役立ちます。質問、および質問が参照している図:
3170 次
2 に答える
2
私はあなたの間違いを指摘しようとします。
このアルゴリズムは BFS のようにグラフをトラバースすると思いました
本当じゃない。このアルゴリズムは、グラフのすべてのエッジを繰り返し反復し、安定した状態になるまでそれらを「緩和」します (緩和を行うことができなくなったとき)。
添付した例は少しわかりにくく、BFS の実行に似ています。これは、各反復で、ノードの値に影響を与えたエッジ (緩和されたエッジ) のみを太字にしたためです。
したがって、あなたの質問に答えるには、エッジの順序を選択し、いわゆる「リラックス」を開始します。各エッジについて、そのポインティング ノード d 値を Z からの最短距離に設定し、その pi を先行ノードに設定します。すべての値が安定するまでこれを繰り返します。
それがあなたの質問に答えることを願っています。
于 2011-11-27T10:03:54.010 に答える