ダイクストラ法とは？
ダイクストラ法とは、重み付きグラフで、ある1点から他の全点への最短経路を求めるアルゴリズム。未確定の点のうち始点からの暫定距離が最小の点を確定させ、その隣接点の距離を更新する手順を繰り返す。局所的に最小のものを選び続けるので貪欲法の一種に分類される。
だいくすとらほう
ダイクストラ法の意味
重み付きグラフで、ある1点から他の全点への最短経路を求めるアルゴリズム。未確定の点のうち始点からの暫定距離が最小の点を確定させ、その隣接点の距離を更新する手順を繰り返す。局所的に最小のものを選び続けるので貪欲法の一種に分類される。
ダイクストラ法の具体例
ルーティングプロトコルOSPFが、リンクコストを重みとしてこの方式で最短経路木を作る。カーナビの経路探索や、工程の最短所要時間の算出にも同じ考え方が使われる。
ダイクストラ法は試験でどう引っ掛けられる？
重みに負の値があると誤った結果を返す（この場合はベルマン・フォード法）。また求まるのは「最短経路長」であって、経路そのものを出すには直前の点を記録しておく必要がある。
ダイクストラ法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。