単一始点最短路(Dijkstra)
説明
負辺のない単一始点全点間最短路を求めるアルゴリズム。負辺が無いと仮定すると、各地点でもっとも近いところから距離が確定していく。距離順でソートされたヒープを用いると、効率よく距離を確定していくことができる。
使い方
- Dijkstra(g, s): 重み付き有向グラフ $g$ 上で, 頂点 $s$ からすべての頂点への最短距離を求め, その列を返す。
計算量
$O(E \log V)$
$V$: 頂点数, $E$: 辺数
実装例
応用: 牛ゲー
単一始点最短路は特殊な線形計画問題の双対である(いわゆる牛ゲー)。
頂点 $s$ から頂点 $v$ までの最短経路を $f(v)$ とする。グラフに負閉路がなければ $f(s) = 0$ である。また頂点 $u$ から $v$ へ向かう重み $w$ の辺が存在するとき $f(u) + w \ge f(v)$ が成立する。言い換えれば, 頂点 $v$ には最大でも $f(u) + w$ のコストで到達可能を意味していて, これは明らか。
最短路問題を解くことで各 $v$ について $f(v)$ がとりうる最大の値を求めることができる。つまり $f(v)$ の最大値を求める問題が最短路問題に対応する。
すべての制約が 変数+定数≧変数 の形で表される線形計画問題は, 対応するグラフ上での最短路問題を解くことで求めることが出来る。$f(u) + w \ge f(v)$ が成立するとき, 頂点 $u$ から頂点 $v$ へ向かう重み $w$ の辺を張れば良い。
問題例
- 検証済AOJ GPL_1_A 単一始点最短経路
- AOJ0212 高速バス
- AOJ1156 ちょろちょろロボット
- AOJ2151 Brave Princess Revisited
- AOJ0596 タクシー
- AOJ1138 Traveling by Stagecoach
- AOJ1150 崖登り
- AOJ2021 お姫様の危機
- AOJ0155 スパイダー人 (経路復元)
- AOJ0562 JOI 国の買い物事情
- AOJ1162 離散的速度
- AOJ2672 郵便局員を救え
- AOJ0601 フクロモモンガ
- AOJ0605 現代的な屋敷
- AOJ1183 鎖中経路
- AOJ2585 一日乗車券