Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

Dijkstra法に関するn考察 〜前半〜

(思ったより長くなりそうだったので前半と後半に分けることにしました。 後半の投稿予定は未定です。)

競技プログラミングのグラフ問題でしばしば題材となるアルゴリズムDijkstra法」。 その名前のインパクトと汎用性から比較的知名度が高いアルゴリズムだが、実装がそこそこ重いため初心者の壁となることもある。

そんなDijkstra法について、私の持つ知識、イメージを適当に書き連ねていこうと思う。

目次

Dijkstra法の概要

何をするアルゴリズム

Dijkstra法を一言で説明するなら「重み付きグラフにおいて、ある頂点から他の全ての頂点までの最短距離を求める」アルゴリズムである。 一工夫すれば最短距離を実現する経路も同時に求められるので、一言に「最短経路を求めるアルゴリズム」とも言える。

ただし制約として、「グラフに負の辺が含まれていると使えない」という点は十分に注意すべきである。負の辺を含む場合は、多少計算量は多いが負の経路検出もできる「Bellman-Ford法」がよく用いられる。

具体例

「最短経路を求めるアルゴリズム」と言ってしまえばそれで終わりなのだが、慣れ親しんでいない方にはいまいち何をしているのかが分かりにくいと思われる。

という訳で、以下に簡単な具体例を示す。 辺の重みを「移動時間」、頂点を「場所」だとしよう。このときグラフ全体は地図のようになっている。

f:id:misteer:20180606142601j:plain

このグラフに対してDijkstra法を用いれば、ある1点(たとえば自宅)から他の全ての場所について、最短移動時間及びその具体的な経路が求まる。

f:id:misteer:20180606142632j:plain

現実の地図では上のように直接アクセスできない場所が存在するなんてことはないが、例えば頂点を「駅」とすれば最短の乗り換え経路を求めることもできる。 この例でもDijkstra法の実用性が高いのがお分かりだろう。

イメージ?

Dijkstra法は、現実におけるどのような事象を再現しているのだろうか? それが分かればDijkstra法が何をしているのかが直感的に理解できるかもしれない。 別に分からなくても実用上の問題は一切ないが、私はDijkstra法を「水の流れ」で捉えている。

「水の流れ」というと「ネットワークフロー」の方を連想する方が多いだろう。「ネットワークフロー」が「ある頂点から別の頂点へ流せる水の最大量」を再現しているように、「Dijkstra法」は「ある頂点に水を注ぎ込んだとき、別の頂点まで水が到達するまでの時間」を再現していると考えられるのがお分かりだろうか。 以下に説明を試みる。


重み付きグラフについて、各頂点を「水槽(容量は無視できるとする)」、辺を「長さが重みだけあるパイプ」と見なしてみる。つまりグラフ全体は「互いにパイプで繋がりあった水槽の集合」となるわけだ。

(図を挿入したいが、正直しんどい)

この水槽のうち1つにホースで水を注ぎ込む。すると、水は水槽に接続されたパイプを通って他の水槽へと流れていく。このとき、水がパイプ内を流れる速度が一定だと仮定すれば、「各水槽へ初めて水が入った時刻」=「最短経路長」となるわけである。

このイメージを使えば、Dijkstra法でやっていることは以下のループとして表現できる:

  1. ある水槽に水が入った時点で一旦時間を止める。
  2. その水槽から別の水槽までどのくらいの時間で水が流れるかを計算する。
  3. 再び時間を再生し、上に戻る。


以上が私がDijkstra法に対して持っているイメージだが、おそらくこれと全く異なるイメージをもっている方もいるだろう。 個人的にどういうイメージがあるのか気になるので、そういった方はコメントにて説明を試みていただけるとありがたい。

実装方法

パターンA

Dijkstra法が動作するときの主な流れは以下の通り:

  1. 始点vからの距離を記録する配列dを用意する。
  2. d[v]を0、他は全部INF(十分大きな値)で初期化する。
  3. 全ての頂点を始点にするまで、以下のループを繰り返す:
    1. 今まで一度も始点としておらず、かつdが最も小さい頂点を始点vとする。
    2. vと繋がっている辺全てについて、以下のように距離を更新する:
      1. 対となる頂点をsv、辺の重みをcとする。
      2. もしd[v] + c < d[sv] (つまり、既存の経路よりもvに寄った方が距離が短い)ならば、d[sv]をd[v] + cで更新する。
// サンプルコードを掲載予定

この通りに実装すれば最短経路が求まる。証明は省かせていただく。(蟻本に証明が載っているのでそちらを参考にすると良いと思われる。根気よく読むべし。)

パターンB (PFS)

しかし、実は上の方法よりも効率の良い実装方法が存在する:

  1. 距離dの初期化の際、始点vごとINFで初期化する。
  2. 訪れるべき頂点をストックするコンテナとして、昇順ソートで(距離, 頂点)のペアを格納するPriority Queueを用意する(以降queとする)。
  3. queに最初に訪れる点として、(0, v)を突っ込む。
  4. queが空になるまで、以下のループを繰り返す:
    1. queの先頭要素を取り出し、距離をc、頂点をvとする。
    2. もしもd[v] < cなら、探索せずループの頭に戻る(すでに探索済みのため)。
    3. d[v]をcで更新する。
    4. vと繋がっている辺全てについて、以下のように距離を更新する:
      1. 対となる頂点をsv、辺の重みをcとする。
      2. (d[v] + c, sv)をqueに突っ込む。
// サンプルコードを掲載予定

Priority Queueが昇順ソートになっていることから、queの一番上のデータは常に距離が一番小さいものになっている。 このようにしてパターンAにおける「頂点探し」の手間を省くことで、計算量を削っている。

ちなみにこの方法は「順位優先探索、PFS (Priority First Search)」と呼ばれることもあるんだとか。

計算量の比較

頂点数をV、辺の数をEとして、2者の計算量を比較してみよう。

パターンAでは、dが最小となる頂点を探すのにO(V)だけかかってしまうことがネックとなり、全体の計算量はO(V^2)となる。

一方パターンBでは、頂点の探索が不要なので計算量はO(ElogV)まで落ちるとのこと。なぜなのかは正直私にもよく分からない。

グラフが密(E = O(V^2))の場合は両者の間に大した差は出ないが、どのみち多くの場合でBの方が高速に作動する。今までAの実装方法しか知らなかった方は、Bの実装方法を身に着けておくと後々役に立つことだろう。

問題例

AtCoderで出題された、Dijkstra法を用いる問題の一例は以下の通り:

ABC020-C「壁抜け」
一見BFSっぽいが、Dijkstra法を使うと「#のコストを決めた場合の移動時間」を求められる。ただし他のテクニックも組み合わせる必要あり。これ本当にC問題か?

ABC022-C「Blue Bird」
すぐにスタートへ戻らないように注意すれば、Dijkstraを繰り返すだけで愚直に解ける。TLEに注意。

ABC035-D「トレジャーハント」
行きと帰りで別々に探索する必要があり、かなり実装重め。

ABC079-D「Wall」
これは比較的素直なDijkstra問題。ただ探索が逆方向なのが少し気持ち悪い。

AtCoderの問題には「アルゴリズムを実装するだけ」みたいな問題はほぼなく、大抵一捻り加えてくるため「勉強したばかりのアルゴリズムを試したい!」という場合にはあまり向いていない。 シンプルにアルゴリズムを練習したいときは「AOJ(Aizu Online Judge)」や「CSA(CS Academy)」がオススメ。

あと調べていて思ったが、AtCoderにはDijkstra法を用いる問題が割と少ない。 数コンテストに1回くらいの頻度で出ている印象だったので結構意外だった。

後半について

後半では他のアルゴリズムとの関係について語りたいと考えているが、具体的な内容はまだ未定である。

後半で取り扱ってほしい内容、この記事の修正点等ありましたら、コメントに書いていただけると極力反映させていただきます。よしなに。