基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。
基本的なグラフ理論の用語については、次を参考にしてください。
グラフ理論 用語集
queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。
C++ STL講習会 by @e869120
最短経路問題とは
一般的に、次のような問題とされます。
$V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニックについても述べていきます。
※以下、頂点数を断りなく $V$, 辺数を断りなく $E$ と表記します。
グラフの表現
競技プログラミングでのグラフ問題では、多くの場合頂点と辺の情報が直接与えられる（以下、ナイーブなグラフと呼びます）か、グリッドとして与えられるかのどちらかです。
当然、一見グラフとは関係のない整数問題などをグラフに帰着する場合も考えられるので、その時は自分でグラフを構築することになりますが、グリッドにすることはほぼないでしょう。
ここでは、最短経路問題の話題の前に、このようなグラフの情報をどう保持するかをまとめます。
グリッドの場合
グリッドの形をしたグラフの場合、95%以上の場合で四方か八方が移動先なので、特に工夫をして保持する必要はありません。もちろん、各マスにグラフとは別の情報がある場合は、それは別のところで2次元配列などを用いて保持することになります。
このように愚直にグリッドを保持する場合、頂点が座標を用いて表現され、頂点を2つの値で処理することになるので、扱いにくい場合があります。このようなときは、頂点のもつ番号を1次元に圧縮してしまう、というのもひとつの手です。
具体的には、グリッドの縦の長さを $H$, 横を $W$ として、上から $i$ 行目、横から $j$ 行目を $(i,j)$ で表現していたのを、$iW+j$ につぶすことができます。$W$ 進法の2桁の整数値とみるイメージです。
このテクニックでグリッドがぐっと扱いやすくなる場合があるので、ぜひ知っておきましょう。
ナイーブなグラフの場合
大きく分けて2つの方法があります。
隣接行列
$V×V$ 行列 $A$ を保持し、頂点 $i$ と頂点 $j$ の間に重み $w$ の辺がある場合、$A_{ij}=w$とします。
辺が存在しない場合、$A_{ij}=\infty$ としたり、例外値（ありえない値）を入れるのが一般的です。
また、重みなしグラフでは、bool値を持たせて、辺が存在するときのみ $A_{ij}=\rm{true}$ とするのもよいです。
使用頻度は少ないですが、特定の問題で絶大な力を発揮することがあります。
短所と長所を挙げます。
短所
- メモリ使用量が多い。（$O(V^2)$ 使います）
- ある頂点からの移動先を列挙する、という操作のコストが大きい（毎回 $O(V)$ かかってしまう)
長所
- ある頂点から他の頂点への間に辺が存在するか、存在するとしたらコストは何か、というデータの取得が $O(1)$ で可能
- のちに説明するワーシャル・フロイド法をはじめとする一部のアルゴリズムで非常に有用
といった感じです。
隣接リスト
ある頂点から出ている辺をすべて頂点に紐づけて管理します。
具体的には、頂点の数だけ可変長配列（C++ではstd::vector）を用意し、辺の情報をすべてそこに詰め込みます。重みなしなら先の頂点番号だけを、重みがあるなら両方をセットにして保持します。ここで、可変長配列を使わないと空間計算量が $O(VE)$となり、爆発するので要注意です。
同様に短所と長所を挙げます。
短所
- ある頂点から他の頂点への間に辺が存在するか、存在するとしたらコストは何か、というデータの取得が $O(1)$ でできない（とはいえ、先にソートしておけば二分探索が可能なので、前処理最悪 $O(V\log E)$ で、毎回最悪 $O(\log E)$ で取得できます）
- ワーシャル・フロイド法で使えない
長所
- メモリ使用量が抑えられる
- 汎用性が非常に高い
結論から言うと、隣接リスト表現が使われることのほうが圧倒的に多いです。
他にも特殊な条件下などで別の表現が使われることもありますが、そのときは逐次説明することにします。
単一始点最短経路問題
さて、前置きが長くなりましたが、ここから本題の最短経路問題の説明に入っていきます。
まずは単一始点最短経路問題からです。
始点が固定されたとき、そこから他の各頂点への最短距離を求める方法をまとめます。
BFS（幅優先探索）
重みなしグラフの単一始点最短経路問題に対して、最も効率的なアルゴリズムです。
アルゴリズム概要は次のとおりです。
- queue（先入れ後出しデータ構造・キュー）を用意する。
- キューに始点の情報をpushする。
- キューが空になるまで、次の操作を繰り返す。
- キューから頂点の情報をひとつ取り出す。
- その頂点から辺をたどって直接行ける頂点を列挙し、もしまだ訪れていない頂点があれば、その頂点に訪れた印をつけ、距離（現在見ている頂点までの距離 $+1$ ）を記録してから、情報をキューにpushする。
この操作が終了したときには、始点から到達可能な全頂点について、距離が記録済みになっています。
BFSの面白いところは、ある頂点をすでに訪れたということと、その頂点への最短距離が求まっているということが同値だということです。なぜか考えてみましょう。
まず、queueからは、必ず頂点が距離の昇順に取り出されます。これはqueueの特性によるものです。
この特性によって、一度訪れた頂点を後から訪れるときは、そこへの距離が短く更新されることはなくなります。よって、効率的に探索できます。
計算量は $O(E)$ です。
問題例(基本)
問題例
ベルマン・フォード法
重みつきグラフの単一始点最短経路問題に対して、おもに負のコストの辺があるときに使われます。
アルゴリズム概要です。
- 辺の情報をすべてひとつの配列にまとめておく。（ここは一般的なグラフの管理の仕方と違います）
- 最短距離が更新されなくなるまで、次の操作を繰り返す。
- 辺をひとつづつ走査して、その辺の始点へのコスト+辺のコストが終点へのコストより小さければ、終点へのコストを更新する。
始点のコストは $0$ に初期化しておき、それ以外の頂点について $\infty$ としておけばよいです。
さて、負の閉路が存在しない場合、このアルゴリズムは停止します。
このとき、任意の頂点への最短経路は、同じ頂点を2度通らないので、通る辺は高々 $V-1$ 本です。
よって、上の概要に書いてある辺走査を最大 $V-1$ 回だけ行えば最短距離が更新されます。
逆に、$V$ 回目の更新が発生すれば、始点から到達できる位置に必ず負の閉路が存在することがわかります。
以上より、最悪計算量は $O(VE)$ で、負閉路の検出に使えます。
負の辺を含まない場合は次に紹介するダイクストラ法のほうが高速なので使われない場合も多いですが、負の辺を含む重みつきグラフに対しては非常に有効なアルゴリズムです。
使う場面はそこまで多くないですが、以下のような問題で活用できます。
問題例(基本)
問題例
ダイクストラ法
負の辺を含まない重み付きグラフの単一始点最短経路問題に対して使われます。
俗に拡張ダイクストラと呼ばれる、グラフの持つ情報を拡張して使われる場合もあり、最も使用頻度が高いといっても過言ではありません。
発想としてはBFSに近いです。
- priority_queue（優先度キュー）を用意し、始点の情報とそこへの最短距離（始点なら $0$ ）をpushする。このとき、最短距離順で情報がソートされるようにする。
- キューが空になるまで、次の操作を繰り返す。
- キューの先頭要素（最短距離の一番小さいもの）を取り出す。
- もし、記録してある最短距離より取り出した要素に入っている距離情報のほうが大きければ、ここで打ち切って先頭要素を取り出す操作に戻る。
- そこから移動できる頂点を走査し、最短距離が更新できるものがあれば、距離を更新してからその頂点への距離、頂点の情報をキューにpushする。
BFSと同じような発想で、priority_queueを利用することにより、キューの先頭にある要素の最短距離は、この後どれだけ更新を行っても変化することはありません。（負の辺が存在しないので、それ以外の頂点からの更新でこれ以上距離が短くなることがないです）
計算量は $O(E\log V)$ です。
使える問題はたくさんあります。例えば、以下のようなものです。
問題例(基本)
問題例
- JOI 2008 予選 6 - 船旅
- SoundHound Inc. Programming Contest 2018 -Masters Tournament--D Saving Snuuk
- 技術室奥プログラミングコンテスト #4 Day1 - don't be late
- JOI 2014 予選 5 - タクシー
- JOI 2016 予選 5 - ゾンビ島
全頂点対最短経路問題
任意の2頂点の対に対して最短経路を求める方法です。
基本的には、時間計算量 $O(V^3)$ のワーシャル・フロイド法が使われることが多いですが、ダイクストラ法をすべての頂点について行えば $O(VE\log V)$ で解けるはずです。
また、木上での全頂点対最短経路問題は、LCA(Lowest Common Ancestor)を使ったアルゴリズムを使えば、前計算 $O(V)$, クエリごとで $O(\log V)$ で解けます。
ここではこれらの方法も紹介します。
ワーシャル・フロイド法
実装が非常に簡単です。あまり使用頻度は高くありませんが、重要なアルゴリズムです。
動的計画法を使って問題を解きます。
$\rm dp[k][i][j]$ を、$0$ から $k-1$ までの頂点を使って $\rm i$ から $\rm j$ まで移動するときの最小コスト、と定義します。
$\rm dp[0][i][j]$ は、当然 $i$ から $j$ までの距離と等しいです。（辺が存在しない場合は $\infty$ とします）
$\rm dp[k+1][i][j]$ を求めることを考えます。
もし $i$ から $j$ までの最短経路が頂点 $k$ を含まない場合、$\rm dp[k+1][i][j]=dp[k][i][j]$ です。
頂点 $k$ を含む場合は、$i$ から $k$ までの最短経路と、$k$ から $j$ までの最短経路に分解できるので、$\rm dp[k+1][i][j]=dp[k][i][k]+dp[k][k][j]$ です。
$\rm k,i,j$ の昇順にループを回せば、$\rm dp[V][i][j]$ は $i$ から $j$ までの最短経路となっています。
このDPでは、更新がかぶる分には何も問題ないので、配列の1次元目を節約することができます。
非常に単純なのでコード例を載せておきます。
for(int k=0;k<V;k++){
for(int i=0;i<V;i++){
for(int j=0;j<V;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
初期値の設定とこのDPだけで最短経路が求まります。
また、あまり関係ないですが、途中で2頂点間の辺の長さが変わるクエリがあっても、$O(V^2)$ で対応できます。
なお、ワーシャルフロイド法は、負のコストの辺がある場合でも解くことができます。例えば、$\rm dp[V][i][i]$ (上のソースコードだと dp[i][i]) が負となるような $i$ が存在すれば、このグラフは負の閉路を含みます。
問題例 (基本)
- 全頂点間最短経路 ※負の閉路を含みます
問題例
木上での全頂点対最短経路問題
木上では、LCA（Lowest Common Ancestor, 最小共通祖先）を求めるアルゴリズムを使って全頂点対の最短経路問題を解くことができます。LCAの解説から始めます。
根付き木において、ある2頂点の共通祖先（2頂点から根までのパス両方の上にある頂点）のうち、いちばん根から遠いものをLCA,最小共通祖先と呼びます。
木上の2頂点 $u,v$ の距離は、
（根から $u$ までの距離）$+$（根から $v$ までの距離）$- 2$（根から $u,v$ のLCAまでの距離）
です。
根から各頂点までの距離は、DFSやBFSなどを行って、$O(V)$ で簡単に求められます。
木において、最小共通祖先を求めるのは前処理 $O(V)$ または $O(V\log V)$, 各クエリ $O(\log V)$ または $O(1)$ で可能なので、前処理だけで高速に任意の2頂点間の最短距離が求められるのです。
以下では、LCAを求めるための2つの主な方法を紹介します。
追記:@rsk0315_h4x さんによると、100000個クエリの問題では、Segment Treeを使うのが1番速かったらしいです。
オイラーツアーとRMQを使う方法
木の根からDFSの探索で訪れた頂点を、その順に記録することをオイラーツアーといいます。
たとえば、上のようなグラフでAからオイラーツアーを行った場合、記録は
A,B,A,C,D,C,E,C,A
という順になります。
オイラーツアーで生成された頂点配列の特徴として、任意の連続する部分列に含まれる頂点集合が部分木になる、ということがあります。
$u$ と $v$ を含み、LCAの祖先を含まない部分木は、最初に $u$ が登場する部分と、最初に $v$ が登場する部分の間の列の集合で表現できます。
この中で最も根からの距離が小さいものを求めれば、それがLCAです。
これはRMQ(Range Minimum Queries)の一種なので、Segment TreeやSparse Tableを使って効率的に解けます。
オイラーツアーにおいて生成される列の長さは辺の数に比例するので、高々 $V$ の定数倍です。
オイラーツアーにおいて根からの距離も記録しておき、最も距離が小さいものを求めれば、Segment Treeでは前処理 $O(V)$（オイラーツアー）、クエリごと $O(\log V)$、Sparse Tableでは 前処理 $O(V\log V)$, クエリごと $O(1)$ でLCAが求められます。
LCAまでの距離だけでなく、どの頂点かも取得したい場合は、RMQのパートで根からの距離とともに頂点番号も記録しないといけないので、注意してください。
ダブリングを使う方法
前処理で次のようなテーブルを構築します。
$\rm doubling[i][j]=j$ から $2^i$ 個頂点をさかのぼった祖先
ここで、$\rm doubling[i+1][j]=doubling[i][doubling[i][j]]$ が成り立つので動的計画法の要領で求めることができ、また、$i$ は高々 $\log V$ 種類しかありえないので、前処理の計算量は $O(V\log V)$ です。
頂点 $u$ と $v$ のLCAを求めるクエリには、次のようにテーブルを用いて対応できます。
- $u$ と $v$ のうち、頂点からの距離が遠い方を、もう一方に合うまでさかのぼらせる。これは、テーブルのうち高々 $\log V$ 個の要素を参照することで実現できる。
- $i$ の降順にテーブルを見ていき、二分探索のような要領で、LCAまで探索範囲を狭めていく。テーブルを $i$ の降順に参照するので、計算量は $O(\log V)$ となる。
こうして、LCAが高速に求められました。前に挙げたオイラーツアーの方法より前処理の計算時間が悪いですが、こちらのほうが実装が軽いことなどを考えると、無用ということはありません。
問題例 (基本)
問題例
- ABC014-D 閉路
- yukicoder No.898 tri-βutree
- JOI 2012 本選 5 - JOI 国のお祭り事情 ※やや難しめ
- Kodamanと愉快な仲間たち-Y 待ち合わせ ※かなり難しめ
経路復元
最短経路を求めるための主なアルゴリズムはここまでです。お疲れさまでした。
ここからは、具体的な最短経路のパスを求める、といった話題に移行します。
ここまでいろいろなアルゴリズムを紹介してきましたが、すべて、ある意味動的計画法のようなアプローチをしてきました。そのため、経路復元は動的計画法の復元と同じような考え方で行えます。
一般的に、動的計画法の復元では、
「A→Bという遷移が存在し、実際にAからBへ遷移を行わせたのと同じ結果がBに記録されているとき、Bまでの遷移ルートの中に、Aが含まれるものが必ず存在する」
ということを利用して復元を行います。
同様に、最短経路問題でも、AからBまでの最短経路長が、AからCまでの経路長とCからBまでの経路長の和になっている場合、AからBへの最短経路のうち、Cを含むものが必ず存在します。
実際の復元では、Cを、Bへの辺を持っている頂点集合から選択し、どんどんAへ向かってさかのぼっていきます。計算量は $O(E)$ です。
問題例
拡張ダイクストラ
俗に「拡張ダイクストラ」と呼ばれる、ダイクストラ法の亜種アルゴリズムについての紹介を最後に行って、記事を締めようと思います。情報オリンピックで超頻出なので、特に中高生は押さえておきましょう。
一部の問題では、一般のダイクストラ法と違って、移動先や頂点の情報にさらなる制約があることがあります。
たとえば、2007年情報オリンピック春合宿3日目第2問 Routeでは、移動する方向に制約があります。
このような場合、priority_queueに追加する情報や、最短距離の記録のために管理する単位（通常は頂点番号のみだが、上の例題ではどこの頂点から来たか、なども管理する必要がある）を拡張することで解くことができます。
拡張ダイクストラでは、どのような情報を追加で管理する必要があるかをしっかり見極めることが大切です。
メモリ使用量もギリギリになることが多いので、メモリを削減する努力も時には必要でしょう。
問題例
おわりに
今回は、競技プログラミングで超頻出の最短経路問題について特集しました。
グラフとして問題が与えられる場合だけでなく、様々なジャンルの最適化問題がグラフの最短経路問題に帰着可能です。グラフの問題を解けるようになるだけでなく、一見関係のない問題をグラフに帰着するスキルも必要ですね。頑張ってください！
では、たのしい競プロライフを！