ダイクストラ法とベルマンフォード法（ルーティングの数理）

2つの最短経路問題

ルーティングの中核は「重み付きグラフ上で、ある始点から各宛先への最短経路を求める」という単一始点最短経路問題です。ノードがルータ、エッジがリンク、重みがコスト（帯域や遅延に基づく値）に対応します。実装上の代表がダイクストラ法とベルマンフォード法で、それぞれリンクステート型と距離ベクタ型のルーティングプロトコルの数学的な核になっています。両者は「同じ最短経路を求める」点で目的が一致しますが、前提・計算量・収束の性質が大きく異なります。

ダイクストラ法：確定済み集合を広げる

ダイクストラ法は、非負の重みを前提に、始点に近いノードから順に最短距離を確定していく貪欲法です。確定済み集合 S に最も距離の小さい未確定ノードを取り込み、その隣接ノードの暫定距離を更新（緩和）する操作を繰り返します。

dist[s] = 0、その他は無限大
未確定ノードを優先度キュー Q に投入
while Q が空でない:
    u = Q から dist 最小のノードを取り出す   # ここで dist[u] が確定
    for each 隣接エッジ (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w            # 緩和
            prev[v] = u

確定の正しさは「非負の重みなら、取り出した時点の最小ノードはそれ以上短くならない」という事実に依存します。負のエッジがあるとこの仮定が崩れ、確定後に短い経路が見つかりうるため、ダイクストラ法は使えません。

ベルマンフォード法：全エッジを繰り返し緩和

ベルマンフォード法は全エッジに対する緩和を V-1 回繰り返します。最短経路はループを含まないため高々 V-1 本のエッジで構成され、各反復で「ホップ数が1つ多い最短経路」まで正しく伝播するからです。

dist[s] = 0、その他は無限大
repeat V-1 回:
    for each エッジ (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
# V 回目でさらに緩和できるなら負閉路あり

負の重みを扱え、V 回目の反復でまだ緩和できれば負の閉路を検出できます。一方で全エッジを V-1 回走査するため計算量は O(V*E) と重くなります。重要なのは、各ノードが始点までの全体地図を知らなくても、隣接ノードの距離だけ知れば自分の距離を更新できる点で、これが分散実装（距離ベクタ型）の理論的根拠になります。

両者の比較

無限カウント問題（カウント・トゥ・インフィニティ）

距離ベクタ型の弱点が無限カウント問題です。あるネットワークがダウンしても、隣接ルータが「自分は2ホップで届く」という（実は自分経由の古い）情報を持っていると、互いの広告を信じ合って距離が 3 → 4 → 5 … と際限なく増え、収束しません。原因は、各ルータが経路の全体像を知らず、隣の言い値を信じるという距離ベクタの構造そのものにあります。

緩和策は次のとおりです。

• 最大ホップ数の上限: RIP は16を到達不能とみなし、増加を打ち切る。これにより無限ループにはならないが、直径の大きい網には使えない。
• スプリットホライズン: 経路を学習したインターフェースには、その経路を広告し返さない。自分発の情報が戻って増殖するのを防ぐ。
• ポイズンリバース: 学習元へはあえて距離無限大で広告し、即座に無効化を伝える。
• ホールドダウン／トリガードアップデート: ダウンを検知したら一定時間は良い情報を受け付けず、変化は即時広告して伝播を速める。

実ネットワークへの接続

ダイクストラ法は OSPF の SPF 計算として、ベルマンフォード法は RIP の距離計算として実装されています。なお EIGRP も距離ベクタ系に分類されますが、内部は素朴なベルマンフォード法ではなく DUAL（Diffusing Update Algorithm）という独自のアルゴリズムで無限カウントを抑える点が異なります。コストの設計はIPアドレスとサブネットの構造に基づく経路集約や、OSI参照モデルの L3 における転送と密接に関わります。アルゴリズムの性質を理解しておくと、収束が遅い・経路が安定しないといった事象を、プロトコルの設計思想にさかのぼって切り分けられるようになります。