ダイクストラ法とは？だいくすとらほう
ダイクストラ法とは、辺に距離や時間などの重みが付いたグラフで、1つの出発点から他のすべての頂点への最短距離を求めるアルゴリズムである。出発点からの暫定距離がいちばん小さい未確定の頂点を確定し、その頂点を経由した場合の距離で隣の頂点の暫定値を更新する、を全頂点が確定するまで繰り返す。辺の重みが負でないことが前提。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →背景
乗換案内やカーナビは「A駅からB駅まで最短何分か」を毎回答えるが、経路を全部列挙すると駅数が増えた瞬間に組合せが爆発する。近いほうから順に確定していけば無駄な経路を見なくて済む、というのが1956年にエドガー・ダイクストラが考えた発想で、後の経路探索の基礎になった。FEでは表を埋めながら確定順と最短距離を答えさせる形で出る。
具体例
駅A→B=5分、A→C=2分、C→B=1分のとき、まずA=0を確定、次に最小のC=2を確定する。Cを経由するとBは2+1=3分になり直行の5分より短いので更新し、B=3で確定。Yahoo!乗換案内やGoogleマップの経路探索も、この考え方を発展させたアルゴリズムで動いている。
試験での引っ掛け
辺の重みに負の値があると正しく解けない点が代表的な出題で、負の辺を扱えるのはベルマンフォード法。また一度確定した頂点の距離はあとから短くならない（重みが非負のときだけ成り立つ性質）。すべての頂点の組の最短距離を一度に求める手法とも別物で、ダイクストラ法は「1つの始点から」である。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。