ぶちのブログ

競プロとCTFが趣味なWebエンジニアのアウトプットの場

ダイクストラ法とワーシャルフロイド法の比較について

追記

Johnsonのアルゴリズムというものがあり、負の重みの辺が存在する場合にも、ダイクストラ法を用いて全点対間最短路問題が解けるそうです。
その場合の計算量解析も、この記事と同じようにできそうです。
この記事の負の辺についての記述は、頑張れば回避はできるけど単純なダイクストラ法ではできない、という風に読んでください。

教えてくださったフォロワーの方、ありがとうございます!

はじめに

ワーシャルフロイド法を使った記憶がほぼないのですが、いくつかの問題をダイクストラ法だけでゴリ押すことができていました。
簡単な計算量解析をしつつ、その2つを比較してみます。

TL;DR

全点対間最短路問題は、一般的にはワーシャルフロイド法で解くが、負の重みの辺が存在しない場合には、ダイクストラ法でも解くことができる。

計算量に注目した場合には、辺の数によってワーシャルフロイド法とダイクストラ法の優劣が決まる。

辺の数が少ない場合にはダイクストラ法が有利で、多い場合にはワーシャルフロイド法が有利。
しかし、辺の数が多い場合も場合もダイクストラ法を用いて、理論上はせいぜい定数倍の悪化で問題を解くことができる。
(実装上は、頂点数をVとしてlogVだけ計算量が悪化し、全体の計算量はO(V^3logV)になることがほとんどだと思われる)

しかし、負の閉路に対応できる点、実装の簡便さを考えると、全点対間最短路問題においてはワーシャルフロイド法が勝ることが多いだろう。

ダイクストラ法を用いた解法の概略

ダイクストラ法は、負の辺がない場合に、ある頂点から各点の最短距離を求めるものである。
ダイクストラ法を、与えられた頂点の回数だけ繰り返すことで、負の辺がない場合の全点対間最短路問題を解くことができる。(参考)

計算量解析

負の辺がない場合について考える。

まず、全点対間最短路問題においては、自己ループと多重辺を適当な枝刈りによって削除できる。よって、単純グラフについてのみ考えれば良い。

頂点の数をV、辺の数をEとする。

ワーシャルフロイド法では計算量はO(V^3)である。

ダイクストラ法の計算量は、二分ヒープを用いた場合にはO((E+V)logV)
フィボナッチヒープを用いた場合にはO(E+VlogV)である、(Wikipedia調べ)
(なお、フィボナッチヒープについてはこちらの記事が興味深かった)

実際には二分ヒープを用いて実装することがほとんどだと思われるので、二分ヒープの計算量O((E+V)logV)を採用する。

単純グラフを仮定したことから、0<=E<=V(V-1)/2である。
よって、最悪の場合の計算量は、ダイクストラ法をV回繰り返すことに注意すると、O(V*(E+V)logV)=O(V^3logV)となる。

また、例えば、E=O(V)の場合には、全体の計算量はO(V^2logV)となり、ワーシャルフロイド法よりも計算量が小さくなる。
このように、辺の数が少ない場合には、定数倍を考えてもダイクストラ法が勝る場合がある。(具体例は後述)

具体例

まず、ワーシャルフロイド法でもダイクストラ法でも解くことができるAtCoderの問題を4つ紹介する。

D - バスと避けられない運命
C - Blue Bird
D - joisino's travel
D - Wall

下の3つの問題については、自分がダイクストラ法を用いて解いた例も貼っておく。

ABC022C 解答例
ABC073D 解答例
ABC079D 解答例

Fastest Codeについて

最後に、それぞれの問題のFastest Code(執筆時)に注目する。

ABC012D Fastest Code
辺の数が多いため、ワーシャルフロイド法である。

ABC022C Fastest Code
単純な全点対間最短路問題ではないため、LCAを用いた解法である。(参考)
ワーシャルフロイド法を用いた最速コードはこちらであり、ダイクストラ法のものよりは高速である。

ABC073D Fastest Code
辺の数が少ないため、ダイクストラ法のほうが高速らしい。

ABC079D Fastest Code
1msの提出がたくさんあるが、それらはすべてワーシャルフロイド法であった。

おわりに

競技プログラミングの範囲では、ダイクストラ法だけでもなんとかなりますが、負の辺がある場合には困ってしまいます。
ちゃんと使い分けることが大事だと分かったので、ワーシャルフロイド法のライブラリを早く作ります!