3

Bellman Ford アルゴリズムは、n-1 回 (n はノードの数) の反復を実行し、各反復でノード間の距離を更新するという説明がありました。すべてのグラフィカルな例は、無限に初期化されたノードと、ソース ノードに最も近いノードが最初の反復で更新されることを示していますが、残りのノードは、それらに到達する反復が発生するまで無限のままです。

ただし、ここで提供されているようなアルゴリズムのコードを見ると、反復回数よりも多くのステップが離れているすべてのノードがアルゴリズムで更新されない理由を理解するのが難しいことがわかります。たとえば、2 回目の繰り返しで、パス abcd を介してのみ到達可能なノード d がある場合、私が読んだ例では、d は 4 回目の繰り返しまで更新されないことを示しているようです。

しかし、コードの主な緩和機能:

def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # Record this lower distance
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

先行ノードのソースからの重みと距離を示す情報に基づいて更新します。アルゴリズムがすべての反復で各ノードを反復する場合、最初の反復で d が適切に更新されないようにするものは何ですか? たとえば、アルゴリズムが abcd の順序でノードを反復処理した場合、アルゴリズムがノード b の距離情報を保存せず、ノード c に移動し、その距離情報を保存し、最終的に d に到達しない理由がわかりません。最初の繰り返しで最短経路を計算するのに十分な情報。

それが何らかの意味を成したことを願っています。

4

1 に答える 1

4

発生する可能性がありますが、保証はされていません。それ以前ではなく、k 番目の反復までの長さの最短パスがあることのみを保証できます。k

ご覧になったビジュアライゼーションは、アルゴリズムの概念を説明するためのものであり、トランザクション メモリ モデルを使用すると、はるかに明確で簡単に理解できます。
最初の反復で距離 10 のノードが変化する場合、視覚化を使用してアルゴリズムを理解するのがどれほど難しいか考えてみてください...

コメントの質問について：

これは、イテレーションごとの変更数を追跡するツールを効果的に作成でき、そのカウンターが 0 に達したら、イテレーションを早期に終了できるということですか?

はい、繰り返しに変更がない場合k-繰り返しk+1は何も変更できず、すべてが最小限でありk+2、...

于 2013-01-16T17:11:03.363 に答える