リンクステート（Link State, LS）アルゴリズム

リンクステートアルゴリズムは、ネットワーク内の全てのルーターが同じネットワークトポロジー情報（リンク状態データベース）を持つことを前提とする、グローバルなルーティング手法です。一般的にはダイクストラ法（Dijkstra's algorithm）が採用され、各ノードは自分を起点とした最短経路ツリーを構築します。

このアルゴリズムの核心は、既に最短経路が確定したノードの集合を拡張しながら、隣接ノードへの距離を反復的に更新していく点にあります。

// 必要なデータ構造
// confirmed_set: 最短経路が確定したノードの集合
// current_cost:  start_nodeから各ノードvへの現在の最小コスト D(v)
// link_weight(a, b): ノードaとbの間のリンクコスト c(a, b)

// 初期化フェーズ
confirmed_set = {start_node};

for (each node v in network) {
    if (v is direct_neighbor of start_node) {
        current_cost[v] = link_weight(start_node, v);
    } else {
        current_cost[v] = INFINITY;
    }
}

// メイン計算ループ
while (confirmed_set.size < total_network_nodes) {
    // 1. 確定集合に含まれないノードの中で、現在のコストが最小のノード w を探索
    candidate_w = find_node_with_min_cost(current_cost, confirmed_set);
    
    // 2. ノード w を確定集合に追加
    add_to_set(confirmed_set, candidate_w);

    // 3. ノード w を経由することで、他のノードへのコストが改善されるかを検証
    for (each neighbor v of candidate_w) {
        // w を経由した場合の新しいコスト計算
        new_path_cost = current_cost[candidate_w] + link_weight(candidate_w, v);
        
        // 既存のコストより低ければ更新
        if (new_path_cost < current_cost[v]) {
            current_cost[v] = new_path_cost;
            // ここで経路の親ノード情報も併せて更新する
        }
    }
}

距離ベクトル（Distance Vector, DV）アルゴリズム

距離ベクトルアルゴリズムは、分散的かつ反復的なアプローチをとります。各ルーターは、隣接ノードとの直接コストと、隣接ノードが保持する「目的地までの距離情報」のみに基づいて、自身のルーティングテーブルを更新します。これはベルマン・フォード方程式（Bellman-Ford equation）に基づいています。

この手法では、ノードはネットワーク全体のトポロジーを知る必要がなく、隣接ノードから受信した距離ベクトル（Distance Vector）を使用して、以下の式に従って最小コストを計算します。

Dx(y) = min { c(x, v) + Dv(y) }

ここで、Dx(y)はノードxから目的地yへの最小コスト、c(x, v)はxから隣接ノードvへの直接コスト、Dv(y)は隣接ノードvが知っているyへの最小コストです。