テクノロジ系 / アルゴリズムとプログラミング
ダイクストラ法
ダイクストラ法は、重みが負でないグラフで、始点から各頂点への最短距離を求めるアルゴリズムです。
別名・関連表記：Dijkstra法
もう少し詳しく
未確定の頂点の中から、始点からの距離が最も小さい頂点を確定し、その頂点から伸びる辺を使って距離を更新します。負の辺がある場合は正しく使えないため、ベルマンフォード法との使い分けが重要です。
試験での見方
例：AからBまで4、AからCまで2、CからBまで1なら、A→C→Bの距離3がA→Bの距離4より短いと更新します。
「負でない重み」「最短距離が小さい頂点を確定」という条件ならダイクストラ法です。表で、確定済み頂点と暫定距離を1段階ずつ更新しましょう。