最短経路問題

最短経路問題は、重み付きグラフで、始点から終点までの辺重み合計が最小となる経路を求める問題です。重みは距離、時間、費用などで、最小全域木とは目的が異なります。

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

• 全辺重みが非負ならDijkstra法で、始点から各頂点への暫定距離が最小の頂点を確定し、隣接辺を緩和します。負辺があると確定済み距離が改善され得るため使えません。

• 負の辺を含む単一始点問題にはBellman-Ford法を使え、始点から到達可能な負閉路も検出できます。負閉路があれば有限の最短経路が定まりません。

• 全頂点対にはFloyd-Warshall法、重みなしグラフには辺数を距離とする幅優先探索を使えます。用途と重み条件で選びます。

• 距離だけでなく直前頂点を記録し、終点から逆にたどって経路を復元します。同距離の最短経路が複数存在する場合もあります。

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

Dijkstra法は負辺不可、Bellman-Ford法は負辺可・負閉路検出、BFSは重みなしという選択が頻出です。

例: 辺$A-B=2$、$A-C=5$、$B-C=1$、$C-D=2$なら、AからDはA-C-Dの7よりA-B-C-Dの$2+1+2=5$が短い経路です。