511
455

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@ageprocpp(ka age)

最短経路問題総特集BFSから拡匵ダむクストラたで

511
Last updated at Posted at 2020-01-18

基本的アルゎリズム幅優先探玢などから応甚経路埩元、拡匵ダむクストラなどたで、最短経路問題に関するアルゎリズムを総特集したした。
基本的なグラフ理論の甚語に぀いおは、次を参考にしおください。
グラフ理論　甚語集
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)$ です。
䜿える問題はたくさんありたす。䟋えば、以䞋のようなものです。

問題䟋(基本)

問題䟋

党頂点察最短経路問題

任意の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が高速に求められたした。前に挙げたオむラヌツアヌの方法より前凊理の蚈算時間が悪いですが、こちらのほうが実装が軜いこずなどを考えるず、無甚ずいうこずはありたせん。

問題䟋 (基本)

問題䟋

経路埩元

最短経路を求めるための䞻なアルゎリズムはここたでです。お疲れさたでした。
ここからは、具䜓的な最短経路のパスを求める、ずいった話題に移行したす。
ここたでいろいろなアルゎリズムを玹介しおきたしたが、すべお、ある意味動的蚈画法のようなアプロヌチをしおきたした。そのため、経路埩元は動的蚈画法の埩元ず同じような考え方で行えたす。
䞀般的に、動的蚈画法の埩元では、
「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に远加する情報や、最短距離の蚘録のために管理する単䜍通垞は頂点番号のみだが、䞊の䟋題ではどこの頂点から来たか、なども管理する必芁があるを拡匵するこずで解くこずができたす。
拡匵ダむクストラでは、どのような情報を远加で管理する必芁があるかをしっかり芋極めるこずが倧切です。
メモリ䜿甚量もギリギリになるこずが倚いので、メモリを削枛する努力も時には必芁でしょう。

問題䟋

おわりに

今回は、競技プログラミングで超頻出の最短経路問題に぀いお特集したした。
グラフずしお問題が䞎えられる堎合だけでなく、様々なゞャンルの最適化問題がグラフの最短経路問題に垰着可胜です。グラフの問題を解けるようになるだけでなく、䞀芋関係のない問題をグラフに垰着するスキルも必芁ですね。頑匵っおください
では、たのしい競プロラむフを

511
455
7

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
511
455

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?