ダイクストラ法とは？

ダイクストラ法とは、重み付きグラフで、1つの始点から各頂点への最短距離を求めるアルゴリズム。始点からの暫定距離が最小の未確定頂点を選んで確定させ、そこを経由した場合の距離で隣接頂点の暫定値を更新する、を繰り返す。優先度付きキューで効率化できる。

だいくすとらほう

情報セキュリティマネジメント試験の頻出用語／テクノロジ系

ダイクストラ法の意味

重み付きグラフで、1つの始点から各頂点への最短距離を求めるアルゴリズム。始点からの暫定距離が最小の未確定頂点を選んで確定させ、そこを経由した場合の距離で隣接頂点の暫定値を更新する、を繰り返す。優先度付きキューで効率化できる。

A→B=5、A→C=2、C→B=1の場合、まずA=0を確定、次に最小のC=2を確定する。Cを経由するとBは2+1=3となり、直行の5より短いので3に更新され、Bは3で確定する。表を作って暫定値を書き換えていくと解きやすい。

辺の重みが負の値だと正しい結果が得られない点が代表的な出題。また一度確定した頂点の距離は後から短くならない（この性質が成立するのは重みが非負のときだけ）。全頂点対の最短経路を一度に求める手法とは別物。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。