ダイクストラ法とは？
ダイクストラ法とは、重み付きグラフで、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／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。