はじめに

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

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

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番目のテーブルは、最短経路で現在の頂点に到達するために取るべき前の頂点を含みます。

重みテーブル

イテレーション	s	1	2	3	4	p
Iter 0	0
Iter 1	0	4		2
Iter 2	0	4	19	-2	4
Iter 3	0	4	19	-2	0	17
Iter 4	0	4	19	-2	0	17
Iter 5	0	4	19	-2	0	17

前のテーブル

イテレーション	s	1	2	3	4	p
Iter 0	-	-	-	-	-	-
Iter 1	-	s	-	s	-	-
Iter 2	-	s	1	1	3	-
Iter 3	-	s	1	1	3	4
Iter 4	-	s	1	1	3	4
Iter 5	-	s	1	1	3	4

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

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