この記事の目的

ダイクストラ法の計算量は、O(ElogV)である。 仮に、エッジの長さが0か1ならばO(E)、つまりエッジの数に比例することになる。 「どうしてそうなるのか全く理解出来ない」と誰でも思うだろう。 優先度キューを使ってBFSで探索していけば、毎回エッジの分だけ分岐があるんだから なんらかの計算量はその分岐がどんどん積み重なっていき、 指数オーダーになってしかるべきだろう。 ふつうの人はそう考える。 どういうメカニズムで探索が省略されているのかなんとなく木を書き出して考えてみても、 なんとなくわかった気になったあとでやっぱりわからんとなる。

それが、ダイクストラ法を題材にしたちょっとした応用問題が出た時に手も足も出なくなる原因である。 グラフがぽいっと渡されて、はいs-t最短距離を計算してくださいと言われたら、 準備していたライブラリに食わせて終わりだが、 よく考えるとグラフ探索に帰着出来るような問題や、 ダイクストラ法を少し拡張したような問題では、たちまち解ける人が減ってしまう。 これは、グラフ系の問題ではよくある話で、クラスカル法の応用だったり、Union Findの応用だったり することはよくある。ダイクストラ法もしかり。

この記事は、「ダイクストラ法ぶっちゃけわからん！」という人のために書いた。 ダイクストラ法で検索すると、たくさんの文章が出てくるが、どれも教科書のようにしっかり書こうとして かえってわかりづらくなっていたり、アルゴリズムの説明に終始していて要点が見えず、 それでは理解が深まらず応用がしにくいのではないかと思うものばかりだった。

優先度キューを使ったダイクストラ法は非常に応用性が高く、動的計画法が想定とされている 問題に対してもグラフ的な見方を与えてくれることがある。 競技プログラミングの初学者にとってなかなか理解しづらいところではあるものの、 深く理解すればそれだけ価値のあるところでもあるのだ。

ダイクストラ法の気持ち = おれは人生最良の日に一度しか働かない

ダイクストラ法では、コストについて昇順で優先度キューで状態を管理して、コストの小さい順にポップして処理していく。

まず、状態とは何か？それは一般にはノードのIDで表されるが、実際にはそれに限らない。

状態は、任意である。二次元でも三次元でも良いし、はたまたboolのような値を持ってもよい。 プログラミングの言葉でいえば、タプル一般である。 最小コストを管理するためのHashMapのキーになるようなものであれば、なんでもよい。

こうして、優先度キューには、(cost, state)が入る。 もし、ポップした時に、そいつが持っているcostがすでに知っているmincost[state]以上ならば、 そいつに関しては探索を進めない。

なぜこんなことが許されるかというと、 ダイクストラ法というのが、各状態が「自分が人生最良の時（つまり自分がとりうるコストが最小の時）」 にたった一度だけ「仕事をする（つまり探索をする）」ことで最適値を探すアルゴリズムだからである。 グラフ探索の様子など考える必要もなく、各々の状態（ノード）が人生最良の時にどう振る舞うかさえ考えればよいのだ。

計算量がなぜO(E)になるのか

だから、計算量は辺の本数に比例する。 なぜかというと、各ノードが人生最良時にたった一度しか探索をせず、 その探索の数の総和が辺の本数の総和だからである。

この計算量の見積もり方を理解すると、応用が効くようになる。 例えば、各状態からたかだか3つ程度しか分岐がないような場合、 計算量はO(3V)で見積もれる。 DPを解くということと最短路問題を解くということは同じであるが、 ダイクストラ法で考えると、より見通しがよくなることがある。

ダイクストラ法が使える条件は何か？

辺のコストは非負でなければならない

よく知られていることとして、ダイクストラ法では、負コストの辺は許されない。 なぜかというと、人生最良の日があとで覆ってはならないからである。

人生最良の日だけ仕事をすれば良いことが許されていること

これは辺コストが非負とほぼ同じだが、ある外部条件に依存して グラフの形状が変わったり、辺コストが変わったりする場合は、 この条件を満たさない。

各状態は次の状態に対するすべての遷移をしないといけない

遷移は網羅的でなければならない。 そうでなくとも、最適値を偶然探し当てることはあり得るかも知れないが・・・。 一生のうちに一日しか働かなくていいのだから、最大限働こう。