ダイクストラ法のリンク集
ダイクストラ法について、参考になる記事や資料をまとめました。
ダイクストラ法は、辺の重みがすべて非負のグラフで、1 つの始点から各頂点への最短距離を求めるアルゴリズムです。「まだ確定していない頂点のうち、暫定の距離が最小のもの」を確定させ、そこから出る辺で隣の頂点の距離を更新する、という操作を繰り返します。優先度付きキュー(二分ヒープ)を使うと 、ヒープを使わずに毎回最小の頂点を探すと です。負の重みの辺があると正しく動かないので、そのときはベルマン-フォード法などを使います。
競プロでよく書く実装では、距離を更新するたびに (距離, 頂点) をキューに追加し、古い要素は消さずに残します。そのため、取り出した距離が記録している距離より大きいときは読み飛ばす処理(if d > dist[v]: continue)が必要です。これがないと計算量が悪化します。また、距離は 64 bit 整数で持つ必要があることが多いです。
AtCoder Library(ACL)にはダイクストラ法がなく、AtCoder Algorithm Lectures にも今のところ最短経路の講座はありません。
まず読むもの
Section titled “まず読むもの”- 最短経路問題総特集!!!
BFSから拡張ダイクストラまで(ageprocpp、Qiita)- BFS、ベルマン-フォード法、ダイクストラ法、ワーシャル-フロイド法、経路復元、拡張ダイクストラ(頂点を増やしたグラフ上のダイクストラ法)までを、文章で順に説明しています。ダイクストラ法の手順には、古い要素を読み飛ばす処理も書かれています。コードはほとんどありません。
- ワーシャル-フロイド法の節の「途中で辺の長さが変わるクエリがあっても で対応できる」は、辺が短くなる場合に限った話です。
- ダイクストラ法による単一始点最短経路を求めるアルゴリズム(アルゴリズムロジック)
- 手順、計算量、C++ の実装、経路復元、正当性の考え方を、図を使って説明しています。
- キューに入れる距離の型が
pair<long, int>のlongです。AtCoder では 64 bit ですが、Windows などでは 32 bit なので、書き写すときはlong longにしてください。
- ダイクストラ法・ダイクストラ法の高速化(アルゴ式)
- 問題を解きながら手順を学ぶ形式です。まずヒープを使わない の方法を実装し、次の問題でヒープを使って高速化します。
注意点と高速化
Section titled “注意点と高速化”- ダイクストラ法のよくあるミスと落し方(snuke)
- 古い要素を読み飛ばす処理を忘れる、最大ヒープのまま使う、負の辺のあるグラフに使う、といったよくあるミスで、実際にどれだけ遅くなるかを撃墜ケースつきで説明しています。自分の実装を確かめるのに役立ちます。
- Dijkstra 法(Kyopro Encyclopedia of Algorithms)
- 定義、計算量、高速化の要点(キューに入れる前の枝刈り、0-1 BFS、拡張したグラフでの利用など)を短くまとめた辞典の項目です。
- 色々なダイクストラ高速化(yosupo、スライド)
- キューに入れる前の枝刈り、辺の重みが のときの 0-1 BFS、重みが小さい整数のときの方法、Radix Heap などの高速化を紹介しています。C++ です。
- 01-BFSのちょっと丁寧な解説(ARMERIA)
- ダイクストラ法、BFS、01-BFS を「暫定の距離が最小の頂点を取り出す」という共通点から説明しています。C++ と Python のコードがあります。
Python
Section titled “Python”- heapq --- ヒープキューアルゴリズム(Python 公式ドキュメント)
heapqは最小ヒープで、(距離, 頂点) のタプルをそのまま入れられます。「優先度キュー実装の注釈」の節では、優先度が変わった要素に無効の印をつけて残し、新しい要素を追加し直す方法を紹介しています。ダイクストラ法で古い要素を読み飛ばすのと同じ考え方です。
- Dijkstra (単一始点最短路)(Luzhiled’s Library)
- C++ の実装で、距離に加えて、直前の頂点と辺の番号を返すので経路復元にも使えます。距離の型はテンプレート引数なので、
long longを指定してください。
- C++ の実装で、距離に加えて、直前の頂点と辺の番号を返すので経路復元にも使えます。距離の型はテンプレート引数なので、
- Yosupo Library Checker - Shortest Path(けんちょんの競プロ精進記録)
- 下の Library Checker の問題の解説で、ダイクストラ法での経路復元の方法を説明しています。C++ のテンプレートつきです。
百科事典・英語の資料
Section titled “百科事典・英語の資料”- ダイクストラ法(日本語版 Wikipedia)
- 擬似コード、ヒープの種類ごとの計算量、ビー玉と紐のたとえによる説明があります。擬似コードはキューの中の値を書き換える(decrease-key)形で、競プロでよく書く「追加して読み飛ばす」形とは違います。
- Dijkstra’s algorithm(英語版 Wikipedia)
- 歴史、擬似コード、正当性の証明、計算量、双方向ダイクストラ法などの変種まで載っています。キューに追加して読み飛ばす形の実装にも触れています。
- Dijkstra - finding shortest paths from given vertex・Dijkstra on sparse graphs(cp-algorithms)
- 前者はヒープを使わない の方法を正当性の証明と経路復元つきで、後者は
setとpriority_queueを使う の方法を説明しています。後者には、読み飛ばす処理がないと まで悪化しうることも書かれています。 - コードは距離を
intで持っています。また、後者でフィボナッチヒープを使った を「理論上の下限」としているのは、比較に基づく方法に限った話です。
- 前者はヒープを使わない の方法を正当性の証明と経路復元つきで、後者は
- Shortest Paths with Non-Negative Edge Weights(USACO Guide)
- 後半がダイクストラ法の節で、C++・Java・Python の実装と問題の一覧があります。読み飛ばす処理を外すと TLE する例も説明しています。前半はベルマン-フォード法とワーシャル-フロイド法です。
- Library Checker - Shortest Path:最短距離と経路を出力します。ライブラリの verify 用です。
- CSES - Shortest Routes I:始点から全頂点への最短距離を求める基本問題です。
- 競プロ典型 90 問 013 - Passing(★5):始点と終点の 2 か所からダイクストラ法を行います。
- ABC035 D - トレジャーハント:行きと、辺を逆向きにしたグラフでの帰りの最短距離を求めます。
- ABC252 E - Road Reduction:各頂点の距離を最後に更新した辺を記録して、最短経路木を作ります。
- ABC164 E - Two Currencies:頂点を (都市, 持っている銀貨の枚数) に増やしたグラフで考えます。
- ABC395 E - Flip Edge:頂点を (頂点, 辺の向きを反転しているか) に増やします。
- ABC325 E - Our clients, please wait a moment:社用車と電車の 2 層のグラフで考えます。完全グラフなので、ヒープを使わない の方法も使えます。
- ABC192 E - Train:出発時刻によって、電車を待つ時間が変わります。早く着くほうが得なので、ふつうのダイクストラ法で解けます。
- ABC204 E - Rush Hour 2:所要時間が出発時刻によって変わり、待つこともできます。各辺で最適な出発時刻を考えます。
- ABC213 E - Stronger Takahashi:コストが か なので、01-BFS でも解けます。
- ABC237 E - Skiing:そのままでは負の辺がありますが、標高を使って辺の重みを非負に変えるとダイクストラ法が使えます。
- ABC211 D - Number of Shortest paths:最短経路の本数を数えます。重みがすべて なので BFS で解けますが、距離が確定する順に本数を足していく考え方はダイクストラ法でも同じです。
- ARC090 E - Avoiding Collision:2 か所からのダイクストラ法で最短経路の本数を数え、2 人が出会う組を除きます。
このブログの記事
Section titled “このブログの記事”- ABC477 E - Wheel Distance
- 中心の頂点から各頂点への最短距離をダイクストラ法で前計算し、各クエリに場合分けで答えています。