読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ワーシャルフロイド法とその例題

ワーシャルフロイド法のアルゴリズムと例題についてまとめておきます。師匠へのレポートもかねて。

ワーシャルフロイド法とは?

ワーシャルフロイド法(Warshall–Floyd Algorithm)とは、グラフの全点間の最短距離を求めるアルゴリズムです。簡単な3重ループを書くだけでグラフの最短路問題が一気に片付いてしまうという優れもの。

ワーシャルフロイド法を使うには、辺の重みを次のように初期化しておきます。(初期化の位置に注意!!→Vを入力で受け取った直後)

int d[MAX_V][MAX_V]; //d[i][j]: i, j間の最短距離
int E, V; //辺の本数, 頂点の個数

void init() {
    REP(i, V) {
        REP(j, V) {
            if (i == j) d[i][j] = 0;
            else        d[i][j] = INF;
        }
    }
}

グラフでは自分から自分までの距離は0, 辺をたどっていくことのできない点どうしの距離はINFと考えます。最初は何も辺がない状態なので、i=jのときだけd[i][j] = 0, 他のときはd[i][j] = INF ですね。

次に、以下のようにグラフを読み込みます(無向グラフの場合)。

void make() {
    REP(i, E) {
        int u, v, c;
        cin >> u >> v >> c;
        u--; v--;
        d[u][v] = c; d[v][u] = c;
    }
}

そしていよいよワーシャルフロイド!

void wf() {
    REP(k, V) {
        REP(i, V) {
            REP(j, V) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

3重ループの中に式を1つ書くだけです。簡単!

この3重ループは、すべての点i, jについて、iからjまで行くときに経由する点kをすべて試しています。もしi->k->jと進んだ方が早ければi->jの最短経路をそれで更新する、というわけです。この3重ループが終わるとd[i][j]にはiからjまでの最短路の長さが全部入ります。*1

3重ループを回しているので、計算量は  O(n^3) です。

例題

ワーシャルフロイド+少しで解ける問題を集めました。ヒントと解答例を注釈につけておいたので、必要な方は使ってください。

D問題ですが、ワーシャルフロイドがあればあとはちょこっと書くだけです。(ヒント:*2

(ヒント:*3

(ヒント:*4

さらに学びたい人へ

実はグラフの最短経路の長さを求める方法はワーシャルフロイドだけではなく、他にも「ダイクストラ法」「ベルマンフォード法」があります。これらの方法はワーシャルフロイドより少しややこしいですが計算量を下げることができるので、 O(n^3)じゃ間に合わない!という時には必要になります。

また、今回は最短路の「長さ」しか求めませんでしたが、「最短経路」を求めることもできます。

これらについては蟻本や以下のサイトが参考になると思います(自分もまだ読んでないのでこれから読みます)

hfuji.hatenablog.jp

*1:かなりざっくりした説明でなのでより詳しく知りたい方はこちらとかご覧ください

*2:場所iに済んだときの「最悪のケース」はiから他の点への最短距離のうち最も大きいものです。なのでdの各行から最大値を求めておき、その中で最も小さいものを答えればOKです:解答例

*3:今度は最大値ではなく総和ですね。1つ上の問題と同じように行ごとに計算して、最小のものを求めましょう:解答例

*4:金額と時間、2種類のコストがあるので、グラフを2つ作ってそれぞれにワーシャルフロイドを適用します:解答例