◉ Dijkstra 法

Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://noshi91.github.io/algorithm-encyclopedia) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /algorithm-encyclopedia/dijkstra#noredirect を利用してください。

name

Dijkstra 法

short description

Dijkstra 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。グラフに負の辺があると動作しない。辺が非負という仮定をもとに動的計画法を利用して高速に動作し、計算量は $O(\vert V \vert ^ 2)$ や $O(\vert E \vert \log \vert V \vert)$ などである。

input

非負の辺重み $c : E \to \lbrace x \in \mathbb{R} \mid x \ge 0 \rbrace$ 付き有向グラフ $G = (V, E)$ および頂点 $s \in V$

output

各頂点 $t \in V$ に対し $s$-$t$ 最短路長

time complexity

$O(\vert V \vert ^ 2)$ や $O(\vert E \vert \log \vert V \vert)$ など

---

概要

Dijkstra 法とは、単一始点最短経路問題を解くアルゴリズムのひとつである。グラフに負の辺があると動作しない。辺が非負という仮定をもとに動的計画法を利用する。 計算量は、単純な実装では $O(\vert V \vert ^ 2)$ である。優先度付きキューを用いる実装では、優先度付きキューに何を使うかに依存し、Binary Heap を用いた場合は $O(\vert E \vert \log \vert V \vert)$ である。

単一始点最短経路問題を解くとは、辺に重みが付いた有向グラフ $G$ と頂点 $s$ が与えられたとき、$s$ を始点とする $s$-$t$ 最短経路をすべての頂点 $t$ に対して求めるということである。

詳細

(省略)

その他

• 高速化のためには優先度付きキューへの push の前の枝刈りが重要である¹。
• Dijkstra 法は辺の重みが整数でかつ最大値が小さいときは優先度付きキューの持ち方を工夫することで計算量を落とせる。この手法は Dial's algorithm と呼ばれる。また特に、辺の重みが $0$ か $1$ のみである場合は 0-1 BFS と呼ばれる¹。
• 辺を逆向きにして終点から Dijkstra 法をするとうまくいくことがある。また、始点と終点の両側からの Dijkstra 法がうまくいくこともある。
• 入力されたグラフを拡張して作った別のグラフ上で Dijkstra 法をするとうまくいくことがよくある。これは「拡張グラフでのダイクストラ法」などと呼ばれる。省略して「拡張ダイクストラ」と呼ばれることもあるが、これは不適切な呼び方であると批判されることが多い²。
• Fibonacci heap を用いて適切に実装すると計算量が $O(\vert E \vert + \vert V \vert \log \vert V \vert)$ に落ちる。これは競技プログラミングの範囲内でもグラフによっては速いことがある³⁴。

参考文献

• Dijkstra, E.W. A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959). https://doi.org/10.1007/BF01386390
  • Dijkstra による提案論文。再発明された Prim 法の紹介も含んでいる。

関連項目

• 動的計画法
  • Dijkstra 法は動的計画法のひとつである。
• Prim 法
  • Prim 法は最小全域木を求めるアルゴリズムのひとつであるが、Dijkstra 法と類似している。
• Bellman-Ford 法
  • Bellman-Ford 法は Dijkstra 法と並ぶ単一始点最短経路問題を解くアルゴリズムのひとつである。Dijkstra 法より遅いが、Dijkstra 法とは違って負辺があっても動作する。
• Shortest Path Faster Algorithm
  • Dijkstra 法を優先度付きキューでなく普通のキューを使うように修正するとほとんど SPFA になる。
• Warshall-Floyd 法
  • Warshall-Floyd 法は全点対間最短経路問題を解くアルゴリズムのひとつである。Dijkstra 法を $\vert V \vert$ 回実行したいような場合には、代わりに Warshall-Floyd 法を使うとよい。
• Dial's algorithm
  • 与えられるグラフの辺の重みが整数でかつ最大値が $k$ のとき、この仮定を使って優先度付きキューの持ち方を工夫することで、Dijkstra 法を修正して計算量は $O(k \vert V \vert + \vert E \vert)$ に落とせる。そのように修正したものが Dial's algorithm である。

外部リンク

• 色々なダイクストラ高速化 - SlideShare^archive.org
  • yosupo によるスライド。必須の高速化テクニック (単純な枝刈り) や、辺の重みの整数性を利用した高速化テクニック (Dial's algorithm) などが紹介されている。
• ダイクストラ法のよくあるミスと落し方 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ^archive.org
  • snuke によるブログ記事。実装ミスをしている Dijkstra 法を撃墜するケースがまとめられている。

注釈

1. 色々なダイクストラ高速化 - SlideShare^archive.org ↩ ↩²

2. https://twitter.com/evima0/status/334678901521530880^archive.org ↩

3. rsk0315 の計測によると AtCoder Regular Contest 064: E - Cosmic Rays^archive.org (完全グラフ) では binary heap より Fibonacci heap の方が速い⁵。(https://twitter.com/rsk0315_h4x/status/1188898280459005954^archive.org) ↩

4. noshi91 の計測によると、Fibonacci Heap が Binary Heap と $O(\lvert V \rvert ^ 2)$ の実装のいずれよりも高速になるようなグラフが存在する。Binary Heap を用いた Dijkstra 法の最悪ケースと Fibonacci Heap の計測 ^archive.org ↩

5. これは binary heap を用いた一般的な $O(\vert E \vert \log \vert V \vert)$ の実装との比較であり、密グラフでは Fibonacci heap を用いた実装より単純な $O(\vert V \vert ^ 2)$ の実装の方が速い場合が多いことに注意せよ。 ↩

---

View full history / Report issues / Edit this page

changelog

• 2021年02月12日「見出し作成」 authors: kimiyuki, reviewers: kuretchi
• 2021年04月03日「Fibonacci Heap の計測の注釈を変更」 authors: noshi91, reviewers:none

license

This work is licensed under a Creative Commons Attribution 4.0 International License.