【C#】ワーシャル-フロイド法の実装をしてみた AtCoder Beginner Contest 051

AtCoder Beginner Contest 051のD問題を解こうとしたらワーシャル-フロイド法に出会ったので実装してみました。

abc051.contest.atcoder.jp

結果

f:id:c_taquna:20190824002653p:plain

コード

github.com

ワーシャル-フロイド法

ダイクストラ法、ベルマンフォード法と同じように、グラフ理論において、最短経路問題を解く時に使うアルゴリズムです。

ja.wikipedia.org

私が知っている最短経路問題を解くアルゴリズムについて使い所を調べてみました。

  • ベルマン-フォード法 → み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。

  • ダイクストラ → グラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである

  • ワーシャル-フロイド法 → 重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。

今回解いたAtCoderの問題も、最初はダイクストラで解こうとしていたのですが、途中で始点を固定しなければならないことに気が付き、どうしようかと調べてみたところ今回のケースはワーシャル-フロイド法がよいことがわかりました。

ワーシャル-フロイド法の理解とD問題の実装

これを見ればワーシャル-フロイド法の挙動は問題なく理解できると思います。 qiita.com

私は、 最短経路の情報を二次元配列で管理して、新しい最短経路が見つかったらその表をアップデートすると理解しました。

このアルゴリズムでは下記の2つの条件にそって初期化をするのが定番(というか、そういうアルゴリズム)のようです。

表に対してINFを入れる 始点・終点が同じ場合はコストを0にする

そして、下記がワーシャル-フロイド法の核となる実装なのですが、この実装で始点(i) - 中継点(k) - 終点(j) のコストを計算し、今入っている値よりも小さければアップデートしていきます。

for (int k = 0; k < N; k++)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
        }
    }
}

ここで、実装で気をつけてほしいところがあります。今回C#で実装しているのですが、初期化処理で下記のような実装をしていました。

for (int i = 0; i < MAX_V; i++)
{
    for (int j = 0; j < MAX_V; j++)
    {
        dist[i, j] = int.MaxValue; // 初期化時に大きな値で埋める
    }
    dist[i, i] = 0;
}

このように初期化処理でint.MaxValueを使用してしまうと、dist[i, k] + dist[k, j]の処理の時にint型の最大値にさらに値を足すこととなり符号が反転してしまいました。そのため、一転して最大値から最小値へとかわってしまいました。なので、今回は1000000という値にしましたが、この値もケースによっては正しい処理が行われない場合もあるかと思います。

まとめ

とりあえず、メモとしてまとめました。下記の実装をC#で書き直したにすぎないので、今回の問題の考え方や詳しい解き方は下記サイトをご参照ください。 drken1215.hatenablog.com