라우팅

import java.util.*;

public class OspfDijkstra {

    // 라우터 그래프: 인접 리스트 (노드, 비용)
    static final int INF = Integer.MAX_VALUE / 2;
    static int N = 6; // A=0, B=1, C=2, D=3, E=4, F=5

    static List<int[]>[] buildGraph() {
        List<int[]>[] graph = new List[N];
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();

        // {인접노드, OSPF비용}
        int[][] edges = {
            {0,1,1}, {1,2,1}, {2,5,1},  // A-B, B-C, C-F
            {0,3,5}, {3,4,1}, {4,5,1},  // A-D(비용5), D-E, E-F
            {1,4,2},                         // B-E(비용2)
        };
        for (int[] e : edges) {
            graph[e[0]].add(new int[]{e[1], e[2]});
            graph[e[1]].add(new int[]{e[0], e[2]});
        }
        return graph;
    }

    // 다익스트라: src에서 모든 노드까지 최단 비용
    static int[] dijkstra(List<int[]>[] graph, int src) {
        int[] dist = new int[N];
        int[] prev = new int[N]; // 경로 역추적용
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[src] = 0;

        // {비용, 노드} — 최소 힙
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );
        pq.offer(new int[]{0, src});

        while (!pq.isEmpty()) {
            int[] cur  = pq.poll();
            int  cost  = cur[0], node = cur[1];
            if (cost > dist[node]) continue; // 이미 처리됨

            for (int[] next : graph[node]) {
                int newCost = dist[node] + next[1];
                if (newCost < dist[next[0]]) {
                    dist[next[0]] = newCost;
                    prev[next[0]] = node;
                    pq.offer(new int[]{newCost, next[0]});
                }
            }
        }
        return dist; // dist[5] = A→F 최단 비용
    }

    public static void main(String[] args) {
        var graph = buildGraph();
        int[] dist = dijkstra(graph, 0); // A=0 출발
        String[] names = {"A","B","C","D","E","F"};
        for (int i = 0; i < N; i++)
            System.out.printf("A→%s: %d%n", names[i], dist[i]);
        // A→F: 3 (A→B→C→F = 1+1+1)
    }
}

from copy import deepcopy

# 그래프: 인접 행렬 (RIP는 홉 수만 사용, 비용은 모두 1)
INF = float('inf')
N   = 6  # A=0, B=1, C=2, D=3, E=4, F=5

adj = [[INF]*N for _ in range(N)]
for i in range(N): adj[i][i] = 0

for a, b in [(0,1),(1,2),(2,5),(0,3),(3,4),(4,5),(1,4)]:
    adj[a][b] = adj[b][a] = 1  # RIP: 홉 수 = 1

# RIP 거리 벡터: 각 라우터의 라우팅 테이블
# dist[i][j] = 라우터 i에서 j까지의 홉 수
dist = [[adj[i][j] for j in range(N)] for i in range(N)]

def rip_update():
    """벨만-포드 기반 거리 벡터 갱신 (한 라운드)"""
    changed = False
    new_dist = deepcopy(dist)
    for i in range(N):           # 각 라우터
        for j in range(N):       # 목적지
            for k in range(N):   # 인접 라우터를 통한 경로
                if adj[i][k] < INF and dist[k][j] < INF:
                    via_k = adj[i][k] + dist[k][j]
                    if via_k < new_dist[i][j]:
                        new_dist[i][j] = via_k
                        changed = True
    dist[:] = new_dist
    return changed

# 수렴할 때까지 반복
names = list("ABCDEF")
for round_num in range(1, 16):  # 최대 15홉 (RIP 제한)
    if not rip_update():
        print(f"라운드 {round_num}에서 수렴")
        break

# A(0)의 최종 라우팅 테이블
print("A의 라우팅 테이블:")
for j in range(N):
    print(f"  → {names[j]}: {dist[0][j]}홉")
# → F: 3홉 (A→B→C→F 또는 A→B→E→F 또는 A→D→E→F)