最短パス:Bellman-Fordアルゴリズム&Floydアルゴリズム

ディレクトリポイントここ:【データ構造とアルゴリズム】関連記事カタログ
Bellman-Fordアルゴリズム:
    Dijckstraアルゴリズムは負の権利図を持つ最短経路を計算するために使用されないので、ここではBellman−Fordアルゴリズムでこの欠点を補う.
    基本思想:前提:もし最も短絡が存在すれば、最も短絡的なリングは存在しない(正環零環は取り除かれ、負環は最も短絡がない).したがって、最も短絡にはn－1つのノードが含まれていますので、n－1ラウンドの緩和操作だけが必要です.複雑度はmnです
    実現コード:(C++)

for(int i = 0; i < n; i++) d[i] = INF;
d[0] = 0;
for(int k = 0; k < n; k++)
  for(int i = 0; i < m; i++) {
    int x = u[i], y = v[i];
    if(d[x] < INF) d[y] = min{d[y], d[x] + w[x][y]};
}

Floydアルゴリズム:
    2つのペアの間の最も短絡を求めて、コードを実現します.

for(int k = 0; k < n; k++)
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if(d[i][j] < INF && d[k][j] < INF) //   k  i j
        d[i][j] = min{d[i][j], d[i][k] + d[k][j]}

    展開:図中にある場合、1を聯通とし、0を非連結とし、 d[i][j]=min｛d[i][j],d[i][k]+d[k]、[j]“”を“改成”する. d[i][j]=d[i][j]𞓜(d[i]&d[k]、[j])「2つの道がつながっているかどうかを求めることができ、その結果、図へのパケット転送があるという.
    巧みな応用例:騒音恐怖症(UVA 10048 Audiophobia)
    この問題は紫書の問題解の誤り(p 365)の問題解の中で「足し算をminに修正し、minをmaxに修正する」ということを見つけました.