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

ワーシャル・フロイド法を使って全点間の最短距離を算出する(グラフ理論)

問題

C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder

ソースコード

解説

AtCoder Beginner Contest 022 解説

ダイクストラ法で解けそうであるが、頂点Aから、どこかにいき再び頂点Aに戻ってくる経路は閉路なためそのままではダイクストラ法やワーシャルフロイド法は使えない。よって以下のように一度頂点Aから頂点Bまでの経路の最短距離を求めるように問題を変換する。

1.「頂点1に隣接する辺を除いたグラフ」の全点 対の最短経路を前計算しておく

2.頂点1に隣接する頂点のうちどの2つを閉路に 含めるか全通り試す

3.前計算した最短経路の結果と合わせて最短閉路 の長さを求める

初めのステップの「「頂点1に隣接する辺を除いたグラフ」の全点 対の最短経路を前計算しておく」という処理にワーシャル・フロイド法を用いる。

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

ワーシャル・フロイド法とは、グラフにおいて、全ての頂点間の最短距離を算出するための方法である。計算量は頂点の数をVとするとO(V2)となる。仕組みは以下のようになる。

  • グラフ内の頂点を3つ取り出しそれをa, b, cとする
  • a → c → b の経路の距離が a → b の経路の距離より小さければ a → b の最短距離を更新する
  • 全てのa, b, cの組み合わせを動的計画法を用いて算出
    dp[任意の頂点1][任意の頂点2] = 2つの頂点間の最短距離
  • 選んだ2つ、または3つの頂点間が繋がっていない場合は距離が最大であると考え無限大とする