최단 경로 — Dijkstra부터 Bellman-Ford까지

시작: S, 목표: 모든 노드까지의 최단 거리

1. dist[S] = 0, 나머지 = ∞
2. 가장 가까운 미확정 노드 u를 선택 (그리디)
3. u의 이웃 v에 대해: dist[v] = min(dist[v], dist[u] + w(u,v))
4. u를 확정 (다시 방문하지 않음)
5. 모든 노드가 확정될 때까지 반복

public static int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // (거리, 노드) min-heap
    PriorityQueue<int[]> pq = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0])
    );
    pq.offer(new int[]{0, start});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];

        // 이미 더 짧은 경로로 확정되었으면 건너뜀
        if (d > dist[u]) continue;

        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            int newDist = dist[u] + w;

            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.offer(new int[]{newDist, v});
            }
        }
    }
    return dist;
}

int[] prev = new int[n];
Arrays.fill(prev, -1);

// 갱신 시
if (newDist < dist[v]) {
    dist[v] = newDist;
    prev[v] = u; // v의 이전 노드는 u
    pq.offer(new int[]{newDist, v});
}

// 경로 복원
public static List<Integer> getPath(int[] prev, int target) {
    List<Integer> path = new ArrayList<>();
    for (int node = target; node != -1; node = prev[node]) {
        path.add(node);
    }
    Collections.reverse(path);
    return path;
}

    A --1--> B
    |         |
    5        -4
    |         |
    v         v
    C --2--> D

dist[B] = 1 (확정) → 하지만 A→C→D→B = 5+2+(-4) = 3... 아니, 이건 -4가 있어도 1이 더 짧네요.
실제 문제가 되는 경우:

    A --1--> B --(-10)--> C
    |                      ^
    +--------5-------------+

A→B→C = 1+(-10) = -9
A→C = 5
Dijkstra: A→C를 5로 확정한 후 B를 처리 → A→B→C = -9인데 이미 확정됨!

public static int[] bellmanFord(int n, int[][] edges, int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // V-1번 반복
    for (int i = 0; i < n - 1; i++) {
        boolean updated = false;

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];

            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }

        if (!updated) break; // 조기 종료 (더 이상 갱신 없으면)
    }

    // 음수 사이클 탐지: V번째 반복에서도 갱신이 일어나면 음수 사이클 존재
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            throw new IllegalStateException("음수 사이클이 존재합니다!");
        }
    }

    return dist;
}

public static int[] spfa(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    boolean[] inQueue = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    inQueue[start] = true;

    while (!queue.isEmpty()) {
        int u = queue.poll();
        inQueue[u] = false;

        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                if (!inQueue[v]) {
                    queue.offer(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    return dist;
}

// 우선순위 = 현재까지의 실제 거리 + 목표까지의 추정 거리
// f(n) = g(n) + h(n)
// g(n): 시작→n 실제 거리
// h(n): n→목표 추정 거리 (휴리스틱)

A --(-1)--> B --(-1)--> C --(-1)--> A

이 사이클을 돌 때마다 거리가 -3씩 줄어듦
→ 무한히 돌면 거리가 -∞
→ "최단 경로" 자체가 정의되지 않음

라우터 A → (cost 10) → 라우터 B → (cost 5) → 라우터 C
라우터 A → (cost 20) → 라우터 C

Dijkstra: A→B→C (cost 15) < A→C (cost 20)
→ C로의 패킷은 B를 경유

가중치가 없는가? → BFS
가중치가 0 또는 1? → 0-1 BFS
양수 가중치만? → Dijkstra
음수 가중치 있음? → Bellman-Ford / SPFA
모든 쌍 최단 경로? → Floyd-Warshall
단일 목표 + 휴리스틱? → A*