最短経路アルゴリズムの体系（ダイクストラ・ベルマンフォード・A*）

共通の土台 ── 緩和と最短経路の構造

最短経路アルゴリズムは見かけが違っても、核は**緩和（relaxation）**という1操作に集約されます。各頂点 v に「始点からの暫定距離 dist[v]」を持たせ、辺 (u, v) を見て dist[u] + w(u,v) < dist[v] なら dist[v] を更新する。これを安全な順序で繰り返すと暫定距離が真の最短距離へ収束します。計算量記法に不安があれば計算量と Big-O 記法を先に押さえてください。

なぜ緩和だけで解けるのか。その根拠が最適部分構造です。始点 s から終点 t への最短経路が頂点 x を通るなら、その経路の s→x 部分もまた s→x の最短経路になっている。途中を別の短い経路に差し替えれば全体も短くできるからです。この性質があるため、部分的に確定した最短距離を足し合わせて全体を組み立てられます。

ただし1つ重大な前提があります。負閉路（一周すると総和が負になる閉路）が経路上に到達可能だと、回るほど距離が減り「最短」が定義できなくなる。各アルゴリズムの適用条件は、突き詰めればこの負の重みをどう扱うかで決まります。

ダイクストラ法 ── 非負重みの貪欲法

ダイクストラ法はすべての辺の重みが非負という前提で動く貪欲法です。確定済み集合の外で dist が最小の頂点を取り出し、それを確定として隣接辺を緩和する。これを全頂点ぶん繰り返します。

dijkstra(s):
  dist[*] = INF; dist[s] = 0
  PQ = {(0, s)}            # 優先度付きキュー（最小ヒープ）
  while PQ not empty:
    (d, u) = PQ.pop_min()  # 暫定距離が最小の頂点を取り出す
    if d > dist[u]: continue   # 古いエントリは捨てる
    for (u, v, w) in edges(u):
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        PQ.push((dist[v], v))

正当性の鍵は「取り出した瞬間にその頂点の距離は確定している」こと。重みが非負なら、いま最小の暫定距離を持つ頂点 u に対し、未確定の他の頂点を経由する経路は必ず u 以上の距離から始まり、そこに非負の重みが積み上がるので u より短くなりようがない。だから u を確定してよい。この論法は負辺があると崩れます。後から大きな負辺で距離が縮む余地が残り、確定が早すぎることになるからです。

計算量は実装で変わります。素朴な配列で毎回最小を線形探索すると O(V²)。二分ヒープによる優先度付きキューを使うと、各辺で最大1回の push（O(log V)）が走り全体で O((V+E) log V) になります。優先度付きキューはここで「次にどの頂点を確定するか」を効率的に選ぶ心臓部であり、その実体であるヒープ構造やデータ構造の計算量がそのまま全体性能を左右します。

ベルマンフォード法 ── 負辺と負閉路の検出

辺に負の重みがあり得るならベルマンフォード法を使います。発想は単純で、全辺の緩和を V-1 回繰り返すだけです。

bellman_ford(s):
  dist[*] = INF; dist[s] = 0
  repeat V-1 times:
    for (u, v, w) in all_edges:
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
  # 負閉路の検出: もう1周して更新が起きるなら負閉路あり
  for (u, v, w) in all_edges:
    if dist[u] + w < dist[v]:
      report "negative cycle reachable"

なぜ V-1 回で十分か。負閉路がなければ、任意の最短経路は同じ頂点を二度通らない単純経路なので辺は高々 V-1 本です。各反復で「最短経路上の少なくとも1本ぶん」が確実に正しく緩和されるので、V-1 回繰り返せば最長の経路でも端まで波及して全頂点が確定します。計算量は反復 V-1 回 × 全辺 E で O(VE)。ダイクストラより遅い代わりに負辺を正しく扱えます。

さらに強力なのが負閉路の検出です。V-1 回で確定したはずなのに、もう1周してまだ更新が起きるなら、それは縮み続ける負閉路が経路上にある証拠です。「最短が定義できない」という事実そのものを検出できる点が実務で効きます。

A* ── ヒューリスティックで探索を絞る

*A（A スター）*はダイクストラの一般化です。ダイクストラが「始点からの実コスト g(v) が小さい頂点」から確定するのに対し、A はゴールまでの推定コスト h(v) を足した f(v) = g(v) + h(v) の小さい頂点を優先します。優先度付きキューの優先度を g から f に差し替えただけ、と見ると本質が掴めます。

# ダイクストラ: PQ の優先度 = g(v)            （始点からの実コスト）
# A*:          PQ の優先度 = g(v) + h(v)       （実コスト + ゴール推定）
#   h ≡ 0 のとき A* はダイクストラに一致する

肝心なのは正当性の条件です。h が許容的（admissible）、すなわちどの頂点でも真の残り距離を過大評価しない(h(v) が実際の残距離以下) なら、A* は最適解を返すことが保証されます。過大評価すると、本当は近いゴールへの経路を「遠そう」と誤って後回しにし、最短でない経路を先に確定してしまう危険があるからです。さらに h が整合的（consistent）、つまり辺ごとに三角不等式 h(u) <= w(u,v) + h(v) を満たすなら、ダイクストラ同様「取り出した頂点は確定」が言え、再展開なしで効率よく解けます。

全体像と選択の指針

3手法は対立物ではなく、前提知識の量で連続的につながった一族です。ベルマンフォードは順序の仮定を置かず全辺を総当たりで緩和する最も汎用な土台。ダイクストラは「非負重み」という前提を加え、確定順序を貪欲に固定して高速化したもの。A* はさらに「ゴール方向の推定値」という前提を足し、探索を目的地へ絞り込んだものです。緩和という共通動作を、どの再帰的・段階的な順序で適用するかの違い、と捉えると体系が一本の線で見えてきます。

選択は機械的に決められます。負辺の可能性があるかでまずベルマンフォード系か否かが割れ、ゴールが1点に決まっていて良い推定値が作れるかで A* かダイクストラかが割れる。漸近計算量だけでなく「どの前提を満たせるか」を起点に選ぶことが、最短経路問題を曖昧さなく解く近道です。