BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
ダイクストラ法
非負の費用を持つ最短経路
ダイクストラ法は、辺の重みが非負のグラフで、一つの開始点から各頂点までの最短距離を求める方法です。まだ確定していない頂点のうち、暫定距離が最小のものを選び、その先の距離を更新します。距離の代わりに時間や費用などを重みとして扱うこともあります。
距離を更新する
開始点の距離を0、それ以外を未到達として始めます。確定した頂点uから隣のvへ進む費用を加え、現在のvの暫定距離より小さければ更新します。この更新を緩和と呼びます。最小の暫定距離を持つ頂点を効率よく選ぶため、優先度付きキューが使われます。
小さな例
AからBへ費用4、AからCへ費用1、CからBへ費用2とします。最初はBが4、Cが1ですが、Cを確定してその先を見ると、Bへは1+2=3で行けると分かります。直接つながる辺の費用だけで経路を決めるのではなく、途中までの累積費用を比較します。
負の重みが問題になる理由
一度最小と判断して確定した後でも、負の辺を通る遠回りで距離が小さくなる可能性があります。そのため、負の重みを含む一般のグラフへ同じ確定手順をそのまま使えません。ベルマン・フォード法など、条件に合う別の方法を検討します。アルゴリズム名を選ぶ前に、重みの条件を確認することが重要です。
経路と距離の違い
最短距離の数値だけでなく実際の道順を返すには、更新したときの直前の頂点を保存します。最後に目的地から開始点へ逆にたどることで経路を復元できます。開始点から到達できない頂点は、距離が未到達のままです。同じ費用の経路が複数ある場合、返す経路は探索順序によって変わることがあります。
試験での追い方
確定済みの集合と各頂点の暫定距離を表にし、最小の頂点を選ぶたびに隣接辺を確認します。幅優先探索は辺の重みが同じ場合に適し、ダイクストラ法は非負の重みを考慮します。選ぶのは最も短い単独の辺ではなく、開始点からの暫定距離が最小の頂点だという点を押さえましょう。
参考資料
内容確認日:2026-11-13