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

最短経路探索は、辺に距離・費用等の重みを持つグラフで、始点から終点までの重み合計が最小となる経路を求める問題です。

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

• ダイクストラ法は未確定頂点のうち始点からの暫定距離が最小の頂点を確定し、辺を緩和します。負の辺を扱えません。

• ベルマン–フォード法は全辺の緩和を繰り返し、負の辺を扱え、始点から到達可能な負閉路も検出できます。

• ワーシャル–フロイド法は動的計画法で全頂点対の最短距離を$O(V^3)$で求めます。

• A*は始点からの実コストと終点までの推定コストを使い、過大評価しないヒューリスティックなら最短性を保って探索を絞れます。

$d[v]\leftarrow\min\left(d[v],\ d[u]+w(u,v)\right)$

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

非負辺の単一始点はダイクストラ、負辺はベルマン–フォード、全頂点対はワーシャル–フロイドです。ダイクストラ法へ負の辺を使わない点が重要です。

例: 距離$d[u]=5$、辺の重み$w(u,v)=3$、現在$d[v]=10$なら、緩和によって$d[v]$を8へ更新します。