テクノロジ
ダイクストラ法とは
読み方：ダイクストラほう
ひとことで言うと：非負重みグラフで、始点から各頂点への最短距離を求めるアルゴリズム。
意味をわかりやすく解説
ダイクストラ法は、辺の重みがすべて0以上のグラフで、一つの始点から各頂点への最短距離を求めるアルゴリズムです。
未確定頂点のうち暫定距離が最小の頂点を確定し、その頂点を経由した場合に隣接頂点の距離が短くなるかを更新（緩和）します。負の重みがあるグラフには原則使えません。
具体例
道路の所要時間がすべて正の値なら、出発地点から各地点への最短所要時間を順に確定できます。
似た用語との違い
覚え方
非負の重みならダイクストラ。「一番近い未確定点から確定」です。
基本情報技術者試験の試験ポイント
負の辺が使えない条件、緩和、確定済み頂点の意味を押さえます。
CHECK QUESTION
負の重みを持つ辺が存在するグラフに、通常のダイクストラ法をそのまま使うべきでない理由は何ですか。
答えを見る
一度最短と確定した距離が、後で負の辺を通る経路によってさらに小さくなる可能性があるためです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。