最短路問題の種類

• 単一始点最短路問題
  • 負の重みがあるグラフ: ベルマン・フォード法
  • 負の重みがない: ダイクストラ法
  • DAG: トポロジカルソートをしてDP
    • 特に木であればただの木上のDP（トポロジカルソート不要）
  • 重みが1: BFS
  • 重みが0か1: 01-BFS
• 全点対間最短路問題
  • ワーシャル・フロイド法

負辺・負閉路の扱い

• 負辺があっても、負閉路がなければ最短路は求まる
• 負閉路があっても、始点から負閉路に到達できなければ最短路は求まる
• 始点から到達可能な負閉路があっても、負閉路から終点に到達できなければ最短路は求まる

最短路の性質

$d(x,y)$ を $x \to y$ の最短路長とする

• 三角不等式 $d(x,z) \leq d(x,y) + d(y,z)$ を満たす
  • もし満たさないならば、$d(x,y)$ は $x\to z$ 最短路長ではないことになるので
• 無向グラフであれば、対称性 $d(x,y) = d(y,x)$ を満たす
  • 有向グラフの場合は満たすとは限らない
• $d(x,y) = 0 \iff x=y$ を満たすかどうかは場合による。

$d$ は距離になっているとは限らない。

ベルマンフォード法

ベルマンフォード法

ダイクストラ法

ダイクストラ法

ワーシャルフロイド法