フォード ベルマン アルゴリズム
n 個の頂点と m 個のエッジ、およびいくつかの開始頂点 v を持つ有向重み付きグラフ G を考えてみましょう。 > 。頂点 v から他のすべての頂点までの最短パスの長さを見つける必要があります。
ダイクストラと同様に、フォード-ベルマン は頂点 1 から他のすべての頂点までの距離を探しますが、負のエッジを処理します.
Ford-Bellman アルゴリズム自体は、いくつかのフェーズ (
n-1) で構成されています。各フェーズで、グラフのすべてのエッジが検査され、アルゴリズムはコスト
c の各エッジ
(a, b) に沿って緩和を試みます。
エッジに沿ったリラクゼーション -mdash;これは、
d[a] の意味を改善する試みです。値
d[b] + c。実際、これはエッジを使用して頂点の答えを改善しようとしていることを意味します。そしてトップの現在の答え
について。
d 配列は、ダイクストラ法と同様に、開始頂点からの最短の長さの配列です。開始頂点を除いて、最初にできるだけ大きな数値を入力します。 0.
エッジを保存するには、隣接行列や重み行列ではなく、エッジがどのノードから出て (
from)、どこに来るのか (
to) を示すリストが使用されます。 code>) とその重み (
cost)。
構造体エッジ {
int from、to、コスト;
};
ベクトル<エッジ>エッジ。
INF 定数は、数値「無限大」を表します。 - 可能なすべてのパス長を明らかに超えるように選択する必要があります。
アルゴリズムの最も単純な実装:
d[v] = 0;
for (int i=0; i
または、構文
C++11 を使用して少し短くすることもできます。
d[v] = 0;
for (int i=0; i
作品例
単純な有向グラフを考えてみましょう。 5 つのノード、重みが 1 の 4 つのエッジがあります。
順番にエッジ一覧を紹介
していきます。
4 5 1
3 4 1
2 3 1
1 2 1
最短の長さの配列の初期値:
<本体>
| 0 |
情報 |
情報 |
情報 |
情報 |
ここで、 inf はエッジの重みよりも常に大きい、一致する整数である必要があります。
1回目の通過後
<本体>
| 0 |
1 |
情報 |
情報 |
情報 |
2回目の通過後
は。
<本体>
| 0 |
1 |
2 |
情報 |
情報 |
3回目以降
は。
<本体>
| 0 |
1 |
2 |
3 |
情報 |
4回目の通過後
<本体>
| 0 |
1 |
2 |
3 |
4 |
エッジを 1 から最後まで順番に供給すると、1 回目のパス後の最短の長さを見つけることができました。