Dijkstra 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /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$ に対して求めるということである。

詳細

(省略)

その他

参考文献

関連項目

外部リンク

注釈

  1. 色々なダイクストラ高速化 - SlideSharearchive.org  2

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

  3. rsk0315 の計測によると AtCoder Regular Contest 064: E - Cosmic Raysarchive.org (完全グラフ) では binary heap より Fibonacci heap の方が速い5。(https://twitter.com/rsk0315_h4x/status/1188898280459005954archive.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)$ の実装の方が速い場合が多いことに注意せよ。