algorithm => ベルマンフォードアルゴリズム

備考

有向グラフGが与えられると、与えられたノードAからグラフ内の残りのノードまでの最短距離を求めることがしばしばあります。 Dijkstraアルゴリズムは最短経路を求める最も有名なアルゴリズムですが、与えられたグラフのエッジ重みが非負である場合にのみ機能します。しかし、 Bellman-Fordは、重みの一部が負であっても、与えられたノード（存在する場合）から最短経路を見つけることを目指しています。負のサイクルがグラフに存在する場合、最短距離が存在しないことがあります（この場合、サイクルを周回することで合計距離が無限に短くなります）。 ベルマンフォードはさらに、このようなサイクルの存在を判断することを可能にする。

アルゴリズムの総複雑さは、 O(V*E)であり、V - は辺の頂点数およびE数である

単一ソース最短経路アルゴリズム（グラフに負のサイクルがあると仮定）

この例を読む前に、エッジリラクゼーションについての簡単なアイデアが必要です。ここから学ぶことができます

Bellman-Fordアルゴリズムは、単一のソース頂点から加重有向グラフ内の他のすべての頂点までの最短経路を計算します。 Dijkstra's Algorithmよりも遅いにもかかわらず、エッジの重みが負であり、グラフ内で負の重みサイクルを検出する場合にも機能します。 Dijkstraのアルゴリズムの問題は、負のサイクルがある場合、サイクルを何度も繰り返し続け、2つの頂点間の距離を減らし続けることです。

このアルゴリズムの考え方は、このグラフのすべてのエッジを何らかのランダムな順序で1つずつ調べることです。ランダムな順序でもかまいません。しかし、 uv （ uとvがグラフの2つの頂点である）がオーダーの1つである場合は、 uからvへのエッジが存在する必要があります。通常、それは与えられた入力の順序から直接取られます。繰り返しますが、ランダムな順序でも動作します。

順序を選択した後、緩和式に従ってエッジを緩和します。 uからvへ向かう所定のエッジuvに対して 、緩和式は次のようになります。

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

つまり、 ソースから任意の頂点u + エッジuvの重みまでの距離がソースから別の頂点vまでの距離よりも小さい場合、 ソースからvまでの距離を更新します。最大で（V-1）回のエッジを緩和する必要があります。ここで、 Vはグラフのエッジの数です。なぜ（V-1）あなたが尋ねる？別の例で説明します。また、頂点の親頂点を追跡する、つまりエッジを緩めるときには、次のように設定します。

parent[v] = u

これは、 u経由でvに達するためのもう一つの短い道を見つけたことを意味します。 ソースから目的の頂点までの最短経路を印刷するには、後でこの機能が必要になります。

例を見てみましょう。グラフがあります：

ソース頂点として1を選択しました。 ソースから他のすべての頂点までの最短経路を探したい。

最初は、ソースであるためd [1] = 0です。そして、私たちはまだ彼らの距離を知らないので、残りは無限です。

このシーケンスでエッジを緩和します：

+--------+--------+--------+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

あなたはあなたが望む任意のシーケンスを取ることができます。エッジを一度リラックスさせると、何が得られますか？ ソースから最大1辺を使用するパスの他のすべての頂点までの距離を取得します。さあ、エッジを緩め、 d []の値を更新しましょう。我々が得る：

d [4] + コスト[4] [5] = 無限 + 7 = 無限大 。これを更新することはできません。
d [2] + コスト[3] [4] = 無限大 。これを更新することはできません。
d [1] + コスト[1] [2] = 0 + 2 = 2 < d [2]となる 。だからd [2] = 2 。また、 parent [2] = 1です。
d [1] + コスト[1] [4] = 4である 。したがって、 d [4] = 4 < d [4] 。 parent [4] = 1です。
d [4] + コスト[4] [6] = 9 。 d [6] = 9 < d [6]となる 。 parent [6] = 4です。
d [2] + コスト[2] [2] = 無限大 。これを更新することはできません。

d[u] + cost[u][v] < d[v]条件が一致しなかったため、一部の頂点を更新できませんでした。前にも述べたように、 ソースから他のノードまでのパスは最大1エッジを使用していました。

私たちの2番目の反復は、2つのノードを使ってパスを提供します。我々が得る：

d [4] + コスト[4] [5] = 12 < d [5]である 。 d [5] = 12となる 。 parent [5] = 4 。
d [3] + コスト[3] [4] = 1 < d [4]である 。 d [4] = 1となる 。 parent [4] = 3です。
d [3]は変わらない。
d [4]は変わらない。
d [4] + コスト[4] [6] = 6 < d [6]となる 。 d [6] = 6である 。 parent [6] = 4です。
d [3]は変わらない。

私たちのグラフは次のようになります：

3回目の反復では頂点5のみが更新され、 d [5]は8になります。私たちのグラフは次のようになります：

これが何回繰り返されても、同じ距離になります。更新が行われるかどうかを確認するフラグを保持します。そうでない場合は、単にループを解除します。私たちの疑似コードは次のようになります：

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

負のサイクルを追跡するために、ここで説明する手順を使用してコードを変更することができます。完成した擬似コードは次のようになります。

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return d

印刷パス：

最短パスを頂点に印刷するには、 NULLを見つけて頂点を印刷するまで親に反復します。疑似コードは次のようになります。

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

複雑：

我々はエッジ最大（V-1）倍を緩和する必要があるため、我々が使用している場合、このアルゴリズムの時間複雑度は、Eはエッジの数を表し、O（Vの*のE）に等しくなるadjacency listグラフを表すために。しかし、 adjacency matrixを使ってグラフを表現すると、時間の複雑さはO（V ^ 3）になります。理由は、 adjacency listが使用されるときO（E）時間内にすべてのエッジを反復することができるが、 adjacency matrixが使用されるときはO（V ^ 2）時間かかる。

なぜ最大限（V-1）回のすべてのエッジを緩和する必要があるのですか？

この例を理解するには、Bellman-Fordの単一ソースの最短経路アルゴリズムについての簡単なアイディアをここで見つけることをお勧めします

Bellman-Fordアルゴリズムでは、最短経路を見つけるために、グラフのすべてのエッジを緩和する必要があります。このプロセスは、最大（V-1）回繰り返され、ここで、 Vはグラフの頂点の数である。

ソースから他のすべての頂点までの最短経路を見つけるために必要な反復回数は、エッジを緩和するために選択する順序に依存します。

例を見てみましょう：

ここで、 ソース頂点は1です。 ソースと他のすべての頂点との間の最短距離がわかります。 頂点4に到達するには、最悪の場合、 （V-1）のエッジを取ることがわかります。今度は、エッジが発見される順序に応じて、 頂点4を発見するのに（V-1）回かかることがあります。それを得ていない？ Bellman-Fordのアルゴリズムを使って最短経路を見つけましょう：

このシーケンスを使用します：

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

最初の繰り返し：

d [3] + コスト[3] [4] = 無限大 。それは何も変わらないでしょう。
d [2] + コスト[2] [3] = 無限大 。それは何も変わらないでしょう。
d [1] + コスト[1] [2] = 2 < d [2]である 。 d [2] = 2となる 。 parent [2] = 1 。

私たちのリラクゼーションプロセスはd [2]だけ変わったことがわかります。私たちのグラフは次のようになります：

2番目の反復：

d [3] + コスト[3] [4] = 無限大 。それは何も変わらないでしょう。
d [2] + コスト[2] [3] = 5 < d [3]となる 。 d [3] = 5である 。 parent [3] = 2。
それは変更されません。

今回は緩和過程が変わった[3] 。私たちのグラフは次のようになります：

3回目の繰り返し：

d [3] + コスト[3] [4] = 7 < d [4] 。 d [4] = 7である 。 parent [4] = 3です。
それは変更されません。
それは変更されません。

私たちの3回目の反復では、最終的に最短経路が1から4になりました。私たちのグラフは次のようになります：

したがって、最短経路を見つけるのに3回の反復が必要でした。この後、何度もエッジを緩めても、 d []の値は同じままです。今、別のシーケンスを考えた場合：

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

私たちは：

d [1] + コスト[1] [2] = 2 < d [2]である 。 d [2] = 2となる 。
d [2] + コスト[2] [3] = 5 < d [3]となる 。 d [3] = 5である 。
d [3] + コスト[3] [4] = 7 < d [4] 。 d [4] = 5である 。

最初の反復では、 ソースから他のすべてのノードまでの最短経路が見つかりました。もう1つのシーケンス1-> 2、3-> 4,2 - > 3が可能であり、これは2回の反復後に最短経路を与える。シーケンスをどのように配置しても、この例ではソースから最短パスを見つけるのに3回以上の時間がかからないという決定に至ることができます。

最善のケースでは、 ソースからの最短経路を見つけるのに1回の反復を要すると結論づけることができます。最悪の場合、それは（V-1）回の反復を取るので、 リラクゼーション （V-1）回のプロセスを繰り返すのです。

負のサイクルをグラフで検出する

この例を理解するには、Bellman-Fordアルゴリズムについての簡単なアイディアをここで見つけることをお勧めします

Bellman-Fordアルゴリズムを使用して、グラフに負のサイクルがあるかどうかを検出できます。最短経路を見つけるには、グラフのすべてのエッジ（V-1）回を緩和する必要があります。ここで、 Vはグラフの頂点の数です。この例では、 （V-1）回の反復の後、反復が何回行われても、 d []を更新することはできません。それとも？

グラフに負のサイクルがある場合、 （V-1）回の反復後であっても、 d []を更新できます。これは、反復ごとに、負のサイクルを通過すると、常に最短パスのコストが減少するためです。これは、Bellman-Fordアルゴリズムが反復回数を（V-1）に制限する理由です。ここでDijkstraのアルゴリズムを使用すると、無限ループに陥ることになります。しかし、負のサイクルを見つけることに集中しよう。

我々はグラフを持っていると仮定しよう：

頂点1をソースとして選択しましょう。 Bellman-Fordの単一ソースの最短経路アルゴリズムをグラフに適用すると、 ソースから他のすべての頂点までの距離がわかります。

これは（V-1） = 3反復後のグラフの様子です。 4つのエッジが存在するため結果が得られます。最短パスを見つけるためには、最大で3回の反復が必要です。したがって、これは答えか、グラフに負の重みサイクルがあります。その（V-1）回の反復の後、我々はもう一度最後の反復を行い、距離が減少し続けるならば、グラフに負の加重サイクルが確実に存在することを意味する。

この例では：我々は2-3をチェックすると、D [2] + コスト[2] [3] [3] D未満である私たちに1を与えるだろう。したがって、グラフには負のサイクルが存在すると結論づけることができます。

では、どうやって負のサイクルを見つけ出すのですか？ Bellman-Fordの手順に少し修正を加える：

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

これは、グラフに負のサイクルがあるかどうかを調べる方法です。ベルマンフォードアルゴリズムを修正して、負のサイクルを追跡することもできます。

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow

algorithm
ベルマンフォードアルゴリズム

サーチ…

備考

単一ソース最短経路アルゴリズム（グラフに負のサイクルがあると仮定）

なぜ最大限（V-1）回のすべてのエッジを緩和する必要があるのですか？

負のサイクルをグラフで検出する