0

Bellman fordアルゴリズムについては以下のページを参照してください（例を示します）。 http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm

まだわかりません。外側のループの最初のループ反復では、例で言うと、最初にエッジ 1->2 とエッジ 1->4 を変更します。エッジ 2->3、2->5、4- を緩和する際の問題は何ですか? d[2] と d[4] があるため、同じステップで >3、4->5 です。

4

1 に答える 1

1

Bellman-Ford のわずかに異なるバージョンを使用すると、この問題は魔法のように消えます。

set toRelax = {initial_vertex}
while toRelax is not empty:
    u = remove a vertex from toRelax
    for each neighbour v of u:
       if we can relax u-v:
          relax u-v
          add v to toRelax

各「ステップ」が 1 つの頂点を含むことに注意してください。「同じステップ」で行われているかどうかは、使用する特定の実装の単なる成果物であり、最終的にアルゴリズムを実際に変更するわけではありません。

于 2011-11-21T16:44:16.310 に答える