最短経路探索

最短経路探索は、重みつきグラフで、出発点から目的地までの重みの合計が最小になる経路を求める方法です。

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

• 負の重みがなければ、ダイクストラ法を使います。

• 負の重みがあれば、ベルマンフォード法を使います。

■ 過去問での着眼点

負の重みの有無で、使う方法を区別します。

例: 乗換え案内で、所要時間が最も短い経路を求めます。