はじめに

ベルマンフォードアルゴリズムは、負のサイクルがない有向グラフ内で、ソースから他のすべての頂点への最短経路を見つける最初のアルゴリズムの1つです。これは動的計画法のアルゴリズムで、グラフのエッジを反復的に緩和します。この記事では、このアルゴリズムを説明するための例を示します！

ベルマンフォードは負のサイクルでは機能しません

負のサイクルは、総重みが厳密に負のサイクルです。この文脈では、AからCに行く場合、無限にAに戻って重みを無限に減らすのが最短経路であると想像できます。ベルマンフォードアルゴリズムは、この場合には明らかに機能しません。

**しかしながら、**アルゴリズムが最短経路を見つけるのに回以上の反復を必要としないことを既に確立しているため、この特性を使用して負のサイクルを検出できます。回の反復後も重みに変化がある場合、グラフに負のサイクルがあることを意味します。

他のアルゴリズムの実装は、反復回数を減らすことができます。

アルゴリズムアルゴリズムを深く掘り下げましょう！

Pythonスタイルの疑似コードでは、次のようにアルゴリズムを実装できます：

def bellman_ford(G: Graph, p: function(int, int) -> int, source: int) -> [prev: List[int], weight: List[int]]:
    '''ベルマンフォードの疑似コード。

    引数: 
        G : Graph : 負のサイクルがないグラフ
        p : function(int, int) -> int : エッジ(u, v)の重みをO(1)で返す関数
        source : int : V内のソース頂点のインデックス
    
    戻り値:
        prev : List[int] : 各頂点の前の頂点を含む配列。
        weight : List[int] : 各頂点について、ソースからこの頂点までの最短経路の重み（重みの合計）を含む配列。
    '''

    # 初期化
    for v in G.vertices:
        weight[v] = inf
        prev[v] = '-'


    weight[source] = 0 # ソースからソースまでの重みは0

    for iter in [1, |V| - 1]: # Wikipediaでの停止条件の証明
        for (u, v) in G.edges:
            if weight[u] + p(u, v) < weight[v]:
                weight[v] = weight[u] + p(u, v)
                prev[v] = u

    return prev, weight

リラクゼーションステップ if weight[u] + p(u, v) < weight[v]: はアルゴリズムの重要なステップです。ここでアルゴリズムは頂点の重みを更新します。

修正された演習

解決策

重みと前の頂点を追跡するために2つのテーブルを作成します。

• 最初のテーブルは頂点の重みを含みます。これは、ソースから頂点までの現在の最短距離に相当します。
• 2番目のテーブルは、最短経路で現在の頂点に到達するために取るべき前の頂点を含みます。

重みテーブル

前のテーブル

経路を計算するには、前のテーブルの最後の行を取ります。

pから、4があります。4から、3があります。3から、1があります。1から、sがあります。