Dial's algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://noshi91.github.io/algorithm-encyclopedia) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /algorithm-encyclopedia/dial#noredirect を利用してください。
name
Dial's algorithm
short description
Dial's algorithm とは、単一始点最短経路問題を解くアルゴリズムのひとつ。非負かつ最大値の小さい整数重みのグラフについてしか動作しないが、重みの最大値を kk として O(kV+E)O(k \vert V \vert + \vert E \vert) で動く。キューの持ち方を工夫して Dijkstra 法をさらに高速化したものになっている。0-1 BFS の一般化でもあり、k=1k = 1 のときは 0-1 BFS に一致する。
input
非負かつ kk 以下で整数値の辺重み c:E{xZ0xk}c : E \to \lbrace x \in \mathbb{Z} \mid 0 \le x \le k \rbrace 付き有向グラフ G=(V,E)G = (V, E) および頂点 sVs \in V
output
各頂点 tVt \in V に対し ss-tt 最短路長
time complexity
O(kV+E)O(k \vert V \vert + \vert E \vert)

概要

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

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

詳細

(省略)

参考文献

関連項目