最短経路探索アルゴリズム

最短経路探索は、辺に距離などの重みがあるグラフで、出発点から目的地までの重みの合計が最小になる経路を求めることです。

■ 試験で押さえるポイント

• ダイクストラ法は、出発点からの距離が確定した頂点を一つずつ増やしていく方法で、負の重みは扱えません。

• ベルマン–フォード法は、負の重みの辺がある場合にも使えます。

• ワーシャル–フロイド法は、全ての頂点の組について最短距離を求めます。

■ 選択肢での判断ポイント

負の重みがなければダイクストラ法、負の重みがあればベルマン–フォード法と使い分けます。

例: Aまでの距離が5、AからBへの辺が3、今のBの距離が10なら、Bの距離を$5+3=8$に更新します。