Floyd-Warshallアルゴリズム

目次

floyd-walshアルゴリズムとは?

アルゴリズム例

では不可能な例

時間複雑度

1.floydwalshアルゴリズムとは?

前述した最短距離アルゴリズムは,開始点を決定しなければならない.
flowersalアルゴリズムは開始点を設定しません.
flowersalアルゴリズムは、すべての頂点間の最短距離を求めるために使用されます.

2.アルゴリズム使用例

上の図を例に挙げましょう.

int n = v.size();
for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
    		for (int j = 1; j<= n; j++)
            		if (D[i][j] > D[i][k] + D[k][j])
                    		D[i][j] = D[i][k] + D[k][j]

以上のコードはfloywalshアルゴリズムを説明した.
次の表を作成して、わかりやすいようにします.

テーブルに表示される行列をD[i][j]と呼ぶ場合、その値は頂点iからjまでの値となる.
D[1][2]の場合、INFは無限であり、頂点1は頂点2と直接関係しないため、INFとして保存される.
kの値を増やしましょう.
kが1の場合、頂点1を通過した最大値が格納されます.

表示される部分が変更されました.
D[2][1]+D[1][3]は既存値D[2][3]よりも値が小さいため、D[2][1]+D[1][3]はD[2][3]の値を修正する.
この手順を繰り返します.頂点ごとに数万ドルです.

後の行列Dは、全ての頂点の最短距離を記憶する.

3.不可能な例

表示されている頂点をチェックすると
1.循環を形成する.
2.形成されたループウェイトの和は負数である.
と確認できます.
この場合、ループが無限である場合、重みの和は無限に小さくなり、最大値は見つかりません.

4.時間の複雑さ

前述のコードを表示できます.
表示するグラフィック頂点をVと呼ぶ場合、時間の複雑さはO(V^3)です.
前述した他のアルゴリズムについてedgeは時間的複雑さに関係する.
従って,エッジの多いグラフィックではflowersalアルゴリズムの動作が見られる.
統合
1.複数の頂点の最短距離を探す必要があります.
2.図のエッジが多数存在します.
この場合、流水アルゴリズムを使用できます.