ダイキストラ法

ウィキペディア

ダイクストラ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/23 10:17 UTC 版)

最短経路問題 > ダイクストラ法

ダイクストラ法の動作のアニメーション

ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

概要

ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。

ほかのアルゴリズムとして、

• 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。
• 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。
• 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。
• 辺の重みに負数を含む場合はベルマン-フォード法がある。

擬似コード

ダイクストラ法の擬似コードは以下の通りである。始点（スタート）から全てのグラフの頂点への最短経路を求める。

• $Q$
  Optimization computes maxima and minima.

非線形(制約付き)

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア