コンテンツにスキップ

ダイクストラ法のリンク集

ダイクストラ法について、参考になる記事や資料をまとめました。

ダイクストラ法は、辺の重みがすべて非負のグラフで、1 つの始点から各頂点への最短距離を求めるアルゴリズムです。「まだ確定していない頂点のうち、暫定の距離が最小のもの」を確定させ、そこから出る辺で隣の頂点の距離を更新する、という操作を繰り返します。優先度付きキュー(二分ヒープ)を使うと O((V+E)log⁡V)O((V + E) \log V)、ヒープを使わずに毎回最小の頂点を探すと O(V2)O(V^2) です。負の重みの辺があると正しく動かないので、そのときはベルマン-フォード法などを使います。

競プロでよく書く実装では、距離を更新するたびに (距離, 頂点) をキューに追加し、古い要素は消さずに残します。そのため、取り出した距離が記録している距離より大きいときは読み飛ばす処理(if d > dist[v]: continue)が必要です。これがないと計算量が悪化します。また、距離は 64 bit 整数で持つ必要があることが多いです。

AtCoder Library(ACL)にはダイクストラ法がなく、AtCoder Algorithm Lectures にも今のところ最短経路の講座はありません。

  • 最短経路問題総特集!!!BFSから拡張ダイクストラまで(ageprocpp、Qiita)
    • BFS、ベルマン-フォード法、ダイクストラ法、ワーシャル-フロイド法、経路復元、拡張ダイクストラ(頂点を増やしたグラフ上のダイクストラ法)までを、文章で順に説明しています。ダイクストラ法の手順には、古い要素を読み飛ばす処理も書かれています。コードはほとんどありません。
    • ワーシャル-フロイド法の節の「途中で辺の長さが変わるクエリがあっても O(V2)O(V^2) で対応できる」は、辺が短くなる場合に限った話です。
  • ダイクストラ法による単一始点最短経路を求めるアルゴリズム(アルゴリズムロジック)
    • 手順、計算量、C++ の実装、経路復元、正当性の考え方を、図を使って説明しています。
    • キューに入れる距離の型が pair<long, int> の long です。AtCoder では 64 bit ですが、Windows などでは 32 bit なので、書き写すときは long long にしてください。
  • ダイクストラ法・ダイクストラ法の高速化(アルゴ式)
    • 問題を解きながら手順を学ぶ形式です。まずヒープを使わない O(N2+M)O(N^2 + M) の方法を実装し、次の問題でヒープを使って高速化します。
  • ダイクストラ法のよくあるミスと落し方(snuke)
    • 古い要素を読み飛ばす処理を忘れる、最大ヒープのまま使う、負の辺のあるグラフに使う、といったよくあるミスで、実際にどれだけ遅くなるかを撃墜ケースつきで説明しています。自分の実装を確かめるのに役立ちます。
  • Dijkstra 法(Kyopro Encyclopedia of Algorithms)
    • 定義、計算量、高速化の要点(キューに入れる前の枝刈り、0-1 BFS、拡張したグラフでの利用など)を短くまとめた辞典の項目です。
  • 色々なダイクストラ高速化(yosupo、スライド)
    • キューに入れる前の枝刈り、辺の重みが 0/10/1 のときの 0-1 BFS、重みが小さい整数のときの方法、Radix Heap などの高速化を紹介しています。C++ です。
  • 01-BFSのちょっと丁寧な解説(ARMERIA)
    • ダイクストラ法、BFS、01-BFS を「暫定の距離が最小の頂点を取り出す」という共通点から説明しています。C++ と Python のコードがあります。
  • heapq --- ヒープキューアルゴリズム(Python 公式ドキュメント)
    • heapq は最小ヒープで、(距離, 頂点) のタプルをそのまま入れられます。「優先度キュー実装の注釈」の節では、優先度が変わった要素に無効の印をつけて残し、新しい要素を追加し直す方法を紹介しています。ダイクストラ法で古い要素を読み飛ばすのと同じ考え方です。
  • Dijkstra (単一始点最短路)(Luzhiled’s Library)
    • C++ の実装で、距離に加えて、直前の頂点と辺の番号を返すので経路復元にも使えます。距離の型はテンプレート引数なので、long long を指定してください。
  • Yosupo Library Checker - Shortest Path(けんちょんの競プロ精進記録)
    • 下の Library Checker の問題の解説で、ダイクストラ法での経路復元の方法を説明しています。C++ のテンプレートつきです。
  • ダイクストラ法(日本語版 Wikipedia)
    • 擬似コード、ヒープの種類ごとの計算量、ビー玉と紐のたとえによる説明があります。擬似コードはキューの中の値を書き換える(decrease-key)形で、競プロでよく書く「追加して読み飛ばす」形とは違います。
  • Dijkstra’s algorithm(英語版 Wikipedia)
    • 歴史、擬似コード、正当性の証明、計算量、双方向ダイクストラ法などの変種まで載っています。キューに追加して読み飛ばす形の実装にも触れています。
  • Dijkstra - finding shortest paths from given vertex・Dijkstra on sparse graphs(cp-algorithms)
    • 前者はヒープを使わない O(n2+m)O(n^2 + m) の方法を正当性の証明と経路復元つきで、後者は set と priority_queue を使う O(mlog⁡n)O(m \log n) の方法を説明しています。後者には、読み飛ばす処理がないと O(nm)O(nm) まで悪化しうることも書かれています。
    • コードは距離を int で持っています。また、後者でフィボナッチヒープを使った O(nlog⁡n+m)O(n \log n + m) を「理論上の下限」としているのは、比較に基づく方法に限った話です。
  • Shortest Paths with Non-Negative Edge Weights(USACO Guide)
    • 後半がダイクストラ法の節で、C++・Java・Python の実装と問題の一覧があります。読み飛ばす処理を外すと TLE する例も説明しています。前半はベルマン-フォード法とワーシャル-フロイド法です。
  • ABC477 E - Wheel Distance
    • 中心の頂点から各頂点への最短距離をダイクストラ法で前計算し、各クエリに場合分けで答えています。