最短経路問題

最短経路問題は、辺に重み（距離や時間）が付いたグラフで、始点から終点までの重みの合計が最小になる経路を求める問題です。

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

• 重みがすべて0以上なら、ダイクストラ法を使います。

• 負の重みがある場合は、ベルマン-フォード法を使います。

• 重みのないグラフでは、幅優先探索で辺の数が最少の経路を求められます。

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

ダイクストラ法は負の重みを扱えない点がよく問われます。

例: A-B＝2、B-C＝1、C-D＝2、A-C＝5なら、AからDへはA-B-C-Dの5が最短です。