ダイクストラ法の計算量と定数倍改善・負の辺・超頂点・頂点倍加・01BFS【競プロ】

この記事では、ダイクストラ法の計算量と定数倍改善、負の辺があるときにダイクストラ法がどうなるか、ダイクストラ法と共によく使われる超頂点と頂点倍加（拡張ダイクストラ法）について扱います。
ダイクストラ法の概要はある程度理解していることを前提とします。（基本的な実装ができれば問題ないです）

この記事の筆者は AtCoder 水色程度の知識しかなく、記事に誤りが含まれる可能性があることをご了承ください。（もちろんできる限り正確に書くように努めています）
間違いの指摘や意見等歓迎しております。X かこの記事のコメント欄にご連絡ください。

この記事では、以下の記号を用います。
$G$ ：非負の重み付きグラフ
$V$ ：グラフ $G$ の頂点数
$E$ ：グラフ $G$ の辺の数

ダイクストラ法の計算量

以下、断りなく「計算量」という単語を用いた場合、最悪時間計算量のことを指します。
ダイクストラ法の計算量を検索すると、 $O(V^2)$ や $O((V+E) \ \log \ V)$ 、 $O(V^2 \ \log \ V)$ などいろいろ出てきます。
これは実装方法やグラフの辺の数によって計算量が変わるためです。

まず、優先度付きキューを使わない素朴な実装の場合、計算量は $O(V^2)$ です。
これは、始点からの距離が最短になっている頂点を探すために毎回 $O(V)$ かけて調べる必要があるためです。

次に、優先度付きキューを使った実装について考えます。
ここで、優先度付きキューは以下の 2 つの操作を $O(\log \ (要素数))$ で行えるものとします。

• 要素の追加
• 最小値の取得・削除

優先度付きキューを使った実装例を示します。

dist = [inf]*(V+1) # 始点からの最短距離を記録する
priority_que = [] # 優先度付きキュー
heappush(priority_que,(0,1)) # 始点は頂点 1 とする
while priority_que:
  # コストが最小の頂点を取り出す
  cost,v = heappop(priority_que)
  if dist[v]<cost: continue
  # 最短距離を確定
  dist[v] = cost
  # 頂点 v と隣接している頂点の最短距離を更新する
  for next_v, next_cost in G[v]:
    if dist[next_v] > cost+next_cost:
      heappush(H,(cost+next_cost, next_v))

各頂点が優先度付きキューから取り出される回数は高々 1 回ずつです。（最短経路に同じ頂点が2度登場することはないため）
つまり、優先度付きキューからコスト最小の頂点を取り出す操作は $V$ 回行われます。
優先度付きキューの要素数は高々 $V$ なので、優先度付きキューからコスト最小の頂点を取り出す操作は全体で $O(V \ \log \ V)$ となります。
次に、優先度付きキューへ要素の追加を考えます。
要素数は高々 $V$ です。
この操作は高々 $E$ 回しか実行されないので、優先度付きキューへ要素の追加は $O(E \ \log \ V)$ です。
したがって、優先度付きキューを使った実装では計算量が $O((V+E) \ \log \ V)$ であることを導けました。
（※厳密には優先度付きキューへの頂点の追加、取得は $E,V$ 回以上になることもありますが、定数倍の範囲です。）

一般的に辺の数は頂点の数と同程度のオーダーである疎なグラフであることが多いので、計算量は $O(V \ \log \ V)$ となります。
しかし、異なる2点がすべて隣接している完全グラフのような密なグラフの場合、辺の数が $V^2$ に近づき計算量は $O(V^2 \ \log \ V)$ となります。
競技プログラミングにおいては、特殊な設定のグラフを考える場合密なグラフになることがあります。
密なグラフにダイクストラ法やBFSを適応したいときに、後述する超頂点や頂点倍加を使い疎なグラフにすることがあります。

ダイクストラ法と負の辺

ダイクストラ法は負の辺がある場合は使えないというのは多くの人が知っていると思いますが、それはなぜでしょうか？
負閉路の有無に分けて考えてみます。
と、その前にダイクストラの重要な点について復習しておきます。

• ある頂点 v が初めて優先度付きキューから取り出されたとき、始点から取り出された頂点 v までの最短距離が確定する。この前提があることで、各頂点は 1 回ずつしか取り出されず、優先度付きキューからコスト最小の頂点を取り出す操作は $V$ (の定数倍) 回に抑えられる。

負の辺あり・負閉路なしの場合

以下のグラフで、頂点 1 から頂点 5 への最短経路をダイクストラ法で求めることを考えます。

非負のグラフと同じようにダイクストラ法を適応し、頂点 1 から頂点 5 への最短距離を確定したときのグラフと優先度付きキューは以下のようになります。（青字が始点からの最短距離）

非負のグラフの場合はこれでダイクストラ法は終了し、頂点 1 から頂点 5 までの最短距離は 4 という解が得られます。
ところが、この時点では負の辺である頂点 2 から 頂点 3 への辺はまだ使われていません。
優先度付きキューから頂点 2 を取り出し、通常通り最短距離の更新と優先度付きキューへの頂点の追加を行うと以下のようになります。


なんと、一度確定したはずの頂点 1 から頂点 3 までの最短距離が、負の辺を通ったことにより再び更新されてしまいました。
そのため、頂点 3 とつながっている頂点 4,5 についても最短距離をもう一度更新する必要があります。

このように負の辺があることによって、ある頂点 v が初めて優先度付きキューから取り出されたとき頂点 v までの最短距離が確定するという前提が崩れ、一度訪れた頂点を何度も訪れ最短距離の更新を何度も行う可能性があります。
負閉路がない場合は最短経路を求めることはできますが、何度も最短経路の更新を行うため通常のダイクストラ法より計算量は悪化します。^[1]

負閉路がある場合

負閉路がある場合、(上記の実装の) ダイクストラ法は終了しません。
なぜなら、負閉路を通るするたびに何度でも最短経路を更新することができるからです。
よってプログラムは無限ループに陥り終了しません。

定数倍改善

実は、はじめに示したダイクストラ法の実装には改善の余地があります。
例えば、以下のグラフにおいて頂点 1 から頂点 4 への最短経路を考えます。（赤字は始点からの最短距離を表します）

このグラフで上記のコードを実行すると、以下の順に実行されます。

このように、頂点 3 は2度訪問されていることがわかります。
2度目の訪問では、最短距離は更新されずループは continue されます。
したがって、2度目の訪問は無駄あり、2度目の訪問のための優先度付きキューへの要素の追加・削除が実行時間を悪化させているとわかります。
改善策として、優先度付きキューへの追加時に暫定的な最短距離を更新することで無駄な訪問の回数を減らすことができます。

その他の定数倍改善テクとしては、最短距離を求めたい頂点を訪問した時点で while ループを break するものがあります。
ある頂点が最初に訪問されるとき始点からその頂点までの最短距離が確定するため、このテクを使っても正しく最短距離が求められます。

上記の 2 つの定数倍改善テクを使ったコードは以下のようになります。

dist = [inf]*(V+1) 
priority_que = [] 
heappush(priority_que,(0,1)) # 始点は頂点 1 とする
while priority_que:
  # コストが最小の頂点を取り出す
  cost,v = heappop(priority_que)
  if v==goal: break # 最短距離を求めたい頂点ならbreak
  if dist[v]<cost: continue # 最短距離でないなら continue
  for next_v, next_cost in G[v]:
    if dist[next_v] > cost+next_cost:
      dist[next_v] = cost+next_cost # 暫定的な最短距離を更新
      heappush(H,(cost+next_cost, next_v))

Python（特にPyPy）ではタプルの比較が遅いため、heapq にタプルを入れると遅くなります。
改善策として、ビットシフトや大きな数字をかけるなどの処理で heapq に入れるものを一次元に圧縮するテクがあります。（圧縮後の整数が 64bit を超えると遅くなるので注意してください）

01BFS

以下の非負の重み付きグラフで頂点 1 から頂点 4 への最短経路を考えます。

この最短経路問題は、重み付きグラフなのでダイクストラ法で解くことができます。
しかし、このグラフの場合は計算量をさらに改善することができます。
このグラフにはコスト 0 と 1 の辺しか存在しません。
そのため、1 つの辺を通っても累計コストは高々 1 しか増えません。
累計コストが高々 1 しか増えないということは、優先度付きキュー内の最大コストと最小コストの差も高々 1 です。（最小コストを取り出し +0 or +1 して優先度付きキューに追加することを繰り返すため）

ちょっとした証明

優先度付きキューから取り出した頂点を v 、頂点 1 から頂点 v までの最小コストを k とします。
取り出した v,k を使って、優先度付きキュー内の最大コストと最小コストの差を 2 以上にするためには以下の 2 つの方法が考えられます。

• コスト 2 以上の辺を通る
• 優先度付きキュー内にコスト k-1 の要素が存在して、コスト 1 の辺を通る

しかし、このグラフではコスト 0 と 1 の辺しか存在しないため 1 つ目の方法は不可能です。
さらに、優先度付きキューから取り出される要素は常にコストが最小なので、優先度付きキュー内にコストが k より小さい要素が存在することもありません。
したがって、優先度付きキュー内の最大コストと最小コストの差も高々 1 であるとわかります。

優先度付きキュー内の最大コストと最小コストの差が高々 1 であるなら、以下の 2 つの操作を行えるデータ構造があれば十分です。

• コストが大きい方の要素の追加と取り出し
• コストが小さい方の要素の追加と取り出し

上記の操作を $O(1)$ で行うことができるデータ構造として deque があります。
deque は筒状のもので左右から要素の追加・取り出しができると考えると、

• コストが大きい方の要素は deque の右側に追加する
• コストが小さい方の要素は deque の左側に追加する

このように要素を追加し、deque の左側の要素を取り出すと常にコスト最小の要素を $O(1)$ で取り出すことができます。
優先度付きキューの代わりに deque を使いダイクストラ法と同じ要領で最短距離を求めると、$O(V+E)$ でこの問題を解くことができます。
ダイクストラ法では $O((V+E) \ \log \ V)$ であったことを考えると計算量を改善できています。^[2]
優先度付きキューの代わりに deque を使うこのアルゴリズムは 01BFS と呼ばれています。
01BFS の実装例を以下に示します。

dist = [inf]*(V+1) 
dq = deque()
dq.append((1,0))
while dq:
  # コストが最小の頂点を取り出す
  cost,v = dq.popleft()
  if v==goal: break 
  if dist[v]<cost: continue 
  for next_v, next_cost in G[v]:
    if dist[next_v] > cost+next_cost:
      dist[next_v] = cost+next_cost 
      if next_cost==1: # コストが増えるなら
        dq.append((cost+next_cost,next_v))
      elif next_cost==0:
        dq.appendleft((cost+next_cost,next_v))

01BFS を使う問題例

• 典型90 043 - Maze Challenge with Lack of Sleep

超頂点

このパートは ABC302-F Merge Set 解法ネタバレを含みます

超頂点とは、中継地点やターミナルのような頂点を追加することで辺の数を抑えたグラフで表現するテクのことです。
ABC302-F Merge Set を例に考えてみます。
この問題をグラフの最短経路問題に落とし込みます。
最も簡単に思いつく方法は、同じ集合内のすべての要素の対に辺を張る、つまり $S_{i,j}$ と $S_{i,k} \ (j≠k)$ の間に辺を張る方法です。
こうすることで、1 から M までの最短距離-1 が求めたい答えになります。
しかし、この方法では辺の数が 1 つの集合につき $O(|S_i|^2)$ 、全体で $O(N^2)$ になってしまいます。
これでは制限時間以内に最短経路を求めるのは不可能です。
辺を減らすことを考えます。
いま同じ集合内のすべての要素の対に辺を張っていますが、共通の要素がある集合を行き来できればよく、集合内のすべての要素の対に辺を張る必要はありません。
そこで、以下の図（入力例1）のように、各集合の要素のを集約する頂点 $S_i$ を新たに用意し、頂点 $S_i$ から集合の各要素について辺を張ります。
新たに追加した頂点が超頂点と呼ばれるものです。

すると、辺の数を $\sum_{i=0}^{N} A_i$ 本に減らすことができました。
あとはこのグラフにおける頂点 1 から頂点 M までの最短経路を求めることでこの問題を AC することができます。^[3]

超頂点を使う問題例

• ABC184-E Third Avenue

頂点倍加

このパートは ABC362-D Shortest Path 3 解法ネタバレを含みます

頂点倍加とは、グラフの頂点を別世界に複製し、元の世界と別世界の行き来にうまくコストを乗せることでうまいことやる方法のことです。^[4]
頂点を複製するので頂点倍加と呼ばれます。
拡張ダイクストラと呼ばれるものと頂点倍加は同義ですが、拡張しているのはダイクストラではなく頂点なので、頂点倍加と呼ぼうという風潮があります。

ABC362-D Shortest Path 3 を例に説明していきます。
頂点 1 から任意の頂点への最短経路を求める問題ですが、頂点自体にコストがありそれを考える必要があります。
これは隣接する頂点に移動する際に「辺のコスト + 移動先の頂点のコスト」を加算することで、ダイクストラを適応し AC することもできますが、せっかくなので頂点倍加を使って解いてみます。
まず、頂点を複製し、「頂点のコストを考慮していない世界の頂点」と「頂点のコストを考慮した世界の頂点」の 2 つを用意します。
そして、頂点のコストを考慮していない世界の頂点 $i$ から 頂点のコストを考慮した世界の頂点 $i$ にコスト $A_i$ の辺を張ります。
さらに、頂点のコストを考慮した世界の頂点 $u$ から 頂点のコストを考慮していない世界の頂点 $v$ にコスト $b$ の辺を張ります。元の辺は無向辺なので、この逆の辺も張ります。
すると、以下のようなグラフが出来上がります。(入力例1)

こうすることで、頂点の重みなど余計なことを考えずにダイクストラ法をそのまま適応できるようになります。
頂点のコストを考慮していない世界の頂点 1 から頂点のコストを考慮した世界の頂点 $i=2',3',\dots, N'$ への最短経路を求ればよいです。
実装では、頂点のコストを考慮した世界の頂点 $v'$ を頂点 $v + N$ とすると簡単に実装できます。

頂点倍加では頂点と辺の数が多くなるため、定数倍が重くなりがちです。
そのため、Python など低速な言語で雑に書くと TLE しがちなので、低速な言語の場合は高速化を意識して書くことをお勧めします。（Python なら入力を高速化する、heapq に入れる要素を一次元化する など）

頂点倍加を使う問題例

• ZONeエナジー プログラミングコンテスト-E 潜入
• ARC061-E すぬけ君の地下鉄旅行

参考

• https://snuke.hatenablog.com/entry/2013/03/01/152108
• https://www-ui.is.s.u-tokyo.ac.jp/~takeo/course/2007/algorithm/dijkstra.pdf
• https://nw.tsuda.ac.jp/lec/dijkstra/
• https://x.com/kyopro_friends/status/1659920317727522817

脚注

1. オーダーレベルで悪化すると思いますが、具体的な計算量については確信を持てなかったのでぼかしています。わかる方いましたら教えてください。

2. $O(V+E)$ は $O((V+E) \ log \ V)$ より速いという主張は、 $O$ 記法の観点から厳密には必ずしも正しいとは限りません。厳密には、ダイクストラ法の計算量は $\Theta((V+E) \ log \ V)$ であり、01BFS は $\Theta(V+E)$ であるため、01BFSの方が高速です。

3. 頂点 1 から頂点 1 が含まれる集合を集約する頂点 $S_i$ に行く分が余分なので、頂点 1 から頂点 M までの最短経路から 1 を引いたものが答えとなることに注意してください。

4. もう少しいい説明があると思います...