Module: Ford-Bellman アルゴリズム


Problem

1/6

フォード・ベルマン: 始まり (C++)

Theory Click to read/hide

フォード ベルマン アルゴリズム
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

最短の長さの配列の初期値:
  <本体>
ここで、 inf はエッジの重みよりも常に大きい、一致する整数である必要があります。

1回目の通過後
 
0 情報 情報 情報 情報
<本体>
2回目の通過後
は。  
0 1 情報 情報 情報
<本体>
3回目以降
は。  
0 1 2 情報 情報
<本体>

4回目の通過後
 
0 1 2 3 情報
<本体>
エッジを 1 から最後まで順番に供給すると、1 回目のパス後の最短の長さを見つけることができました。

 

Problem

プログラムを完成させて、次の問題を正しく解決してください。

複数のエッジとループを持つことができる有向グラフがあるとします。各エッジには、整数 (場合によっては負) で表される重みがあります。負のウェイト サイクルがないことが保証されます。
頂点番号 1 から他のすべての頂点までの最短経路の長さを計算する必要があります。
 
入力
プログラムは最初に数値 N (1 <= N <= 100) – を受け取ります。グラフ頂点の数と数 M (0 <= M <= 10000) –肋骨の数。次の行には、エッジを表す数値のトリプルの M が含まれています: エッジの開始、エッジの終了、および重み (重み – は -100 から 100 までの整数です)。 /div>
 
出力
プログラムは N 個の数字を出力する必要があります –頂点番号 1 からグラフのすべての頂点までの距離。対応する頂点へのパスがない場合は、パスの長さの代わりに数値 30000 を出力します。
 
例
0 1 2 3 4
<頭> <本体>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# 入力 出力
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {         
    }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!