最短経路問題
辺の重みが非負値の2頂点対最短経路問題で、最短経路の距離の下限値が分かっている場合はA*を使うと、ダイクストラ法よりも速く求まる。
最短経路の距離は部分構造最適性が成立しており、下記漸化式が成立する。証明は『アルゴリズムイントロダクション』(ISBN 978-4764904088)などを参照。
V {\displaystyle V} が頂点、 E {\displaystyle E} が辺、 c ( s , v ) {\displaystyle c(s,v)} が辺の重み、 d i s t ( s , v ) {\displaystyle \mathrm {dist} (s,v)} が最短経路の距離。 s , v , w ∈ V {\displaystyle s,v,w\in V} 。 w ≠ s {\displaystyle w\neq s} 。
d i s t ( s , s ) = 0 {\displaystyle \mathrm {dist} (s,s)=0} とおく。
d i s t ( s , w ) = min { d i s t ( s , v ) + c ( v , w ) ∣ ( v , w ) ∈ E } {\displaystyle \mathrm {dist} (s,w)=\min\{\mathrm {dist} (s,v)+c(v,w)\mid (v,w)\in E\}} が成立する。
単一始点の場合 c ( s , v ) = 1 {\displaystyle c(s,v)=1} なら幅優先探索が、 c ( s , v ) ≥ 0 {\displaystyle c(s,v)\geq 0} ならダイクストラ法が、そうでないならベルマン-フォード法が使える。