◉ Dial's algorithm
Kyopro Encyclopedia of Algorithms

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

name: Dial's algorithm
short description: Dial's algorithm とは、単一始点最短経路問題を解くアルゴリズムのひとつ。非負かつ最大値の小さい整数重みのグラフについてしか動作しないが、重みの最大値を $k$ として $O(k \vert V \vert + \vert E \vert)$ で動く。キューの持ち方を工夫して Dijkstra 法をさらに高速化したものになっている。0-1 BFS の一般化でもあり、$k = 1$ のときは 0-1 BFS に一致する。
input: 非負かつ $k$ 以下で整数値の辺重み $c : E \to \lbrace x \in \mathbb{Z} \mid 0 \le x \le k \rbrace$ 付き有向グラフ $G = (V, E)$ および頂点 $s \in V$
output: 各頂点 $t \in V$ に対し $s$-$t$ 最短路長
time complexity: $O(k \vert V \vert + \vert E \vert)$

概要

Dial's algorithm とは、単一始点最短経路問題を解くアルゴリズムのひとつ。非負かつ最大値の小さい整数重みのグラフについてしか動作しないが、重みの最大値を $k$ として $O(k \vert V \vert + \vert E \vert)$ で動く。

Dial's algorithm は、キューの持ち方を工夫して Dijkstra 法を高速化したものになっている。 0-1 BFS の一般化でもあり、$k = 1$ のときは 0-1 BFS に一致する。

(省略)

Robert B. Dial. 1969. Algorithm 360: shortest-path forest with topological ordering [H]. Commun. ACM 12, 11 (Nov. 1969), 632–633. DOI:https://doi.org/10.1145/363269.363610
- Dial による提案論文。始点が複数の形で書かれている。また、Dijkstra 法ではなく SPFA を最適化したものとして説明されている。