Shortest Path Algorithms (최단 경로 알고리즘)

"가중치 그래프에서 출발점이 하나인지 모든 정점 쌍인지, 음수 간선이나 음수 사이클이 있는지에 따라 Dijkstra, Bellman-Ford, Floyd-Warshall 중 무엇을 고르고, 각각은 왜 그 조건에서만 맞는가?" 이 페이지는 그 질문에 답한다. 세 알고리즘은 MST 노트가 그래프의 최소 비용 문제로 드는 "두 정점 사이의 최소 비용 경로 찾기"에 속한다고 볼 수 있다. 이 연결은 이 Wiki의 해석이다. 원문은 이 문제를 모든 정점을 최소 비용으로 잇는 트리 문제, 즉 Graph Algorithms의 MST와 나란히 따로 든다.^[1] 원문 노트 세 개는 각자의 논리적 전제를 적고, Bellman-Ford 노트와 Floyd-Warshall 노트는 다른 알고리즘과의 비교표를 갖고 있으며, 이 페이지는 그것을 하나의 선택 기준으로 묶는다.

선택 표

• 위 표는 Bellman-Ford 노트의 다익스트라 비교표와 Floyd-Warshall 노트의 3종 비교표를 이 Wiki가 한 표로 합친 것이다.^[2][3][4][5]
• 두 비교표의 시간 복잡도 칸은 원문에서 수식 기호가 깨져 있어, 깨지지 않은 hub 노트의 표기로 채웠다.^[6]
• 원문은 음수 간선이 있으면 Dijkstra의 그리디 전제가 깨지므로 Bellman-Ford를 쓰라고 하고, 반대로 음수 간선이 없으면 더 빠른 Dijkstra를 고르라고 한다.^[4:1][7]
• 이 기준을 출발점 조건과 합치면 다음 흐름으로 정리할 수 있다. 이 흐름은 원문 비교표와 위 두 문장을 이 Wiki가 묶은 것이다.

flowchart TD
    Q1{모든 정점 쌍의 거리가 필요한가} -->|예| FW[Floyd-Warshall]
    Q1 -->|아니오: 출발점 하나| Q2{음수 간선이 있거나 음수 사이클을 확인해야 하는가}
    Q2 -->|예| BF[Bellman-Ford]
    Q2 -->|아니오| DJ[Dijkstra]

• Dijkstra는 그리디로, Bellman-Ford와 Floyd-Warshall은 DP로 분류된다.^[8][2:1][9] 그리디와 DP의 적용 조건 차이는 Algorithm Design Strategies가 다룬다.

공통 원리: 거리 갱신 (Relaxation)

• 거리 갱신은 인접 노드로 가는 새 경로 비용이 기존 최단 거리보다 짧을 때만 그 거리를 바꾸는 연산이며, 이를 반복하면 출발점에서 각 정점까지의 최단 거리가 수렴한다.^[10]
• 식으로는 dist[u] + w(u, v) < dist[v]이면 dist[v]를 갱신한다. 원문 식은 기호가 깨져 있어 같은 노트의 코드로 복원했다.^[10:1]
• Bellman-Ford 코드의 간선 완화와 Floyd-Warshall 코드의 점화식 적용도 같은 꼴의 비교와 갱신이다.^[11][12] 세 알고리즘을 "거리 갱신을 어떤 순서로 몇 번 반복하는가"의 차이로 읽는 것은 이 Wiki의 해석이다.

Dijkstra

• Dijkstra는 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 그리디 알고리즘이다.^[8:1]
• 전제는 "지금까지 확보한 최단 경로 중 가장 짧은 경로를 가진 노드는 더 이상 거리가 짧아질 수 없다"는 것이다. 가중치가 모두 양수이므로 한 번 확정된 최단 거리는 이후 갱신되지 않고, 그래서 그리디 선택이 유효하다.^[13]
• 원문은 가중치가 "모두 양수"라는 전제만 적고, 가중치가 0인 간선을 허용하는지는 다루지 않는다.^[13:1]
• 동작 순서는 다음과 같다.^[14]
  1. 출발 노드의 거리를 0, 나머지를 ∞로 초기화한다.
  2. 방문하지 않은 노드 가운데 최단 거리가 가장 짧은 노드를 우선순위 큐(Min-Heap)로 고른다.
  3. 그 노드를 거쳐 인접 노드로 가는 비용이 기존 거리보다 짧으면 갱신한다.
  4. 모든 노드를 방문하거나 큐가 빌 때까지 반복한다.
• 원문 Java 구현은 다음과 같다. 큐에는 {거리, 노드}를 넣고 거리 기준으로 꺼낸다.^[15]

int[] dist = new int[V + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;

// {거리, 노드} 순서로 최소 거리 기준 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, start});

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 nNode = next[0], nCost = next[1];
        if (dist[node] + nCost < dist[nNode]) {
            dist[nNode] = dist[node] + nCost;
            pq.offer(new int[]{dist[nNode], nNode});
        }
    }
}

• 같은 노드는 더 짧은 경로를 찾을 때마다 큐에 다시 들어간다. 그래서 꺼낸 비용이 기록된 거리보다 크면(cost > dist[node]) 이미 처리된 항목으로 보고 건너뛴다.^[15:1]
• 원문 코드는 graph를 선언하지 않는다. 원문 45행 int nNode = next[0], nCost = next[1];로 보아 graph[node]의 원소는 {다음 노드, 가중치} 배열이며, 이 판독은 이 Wiki가 코드를 읽고 덧붙인 것이다.^[15:2]

• 원문은 실전에서 우선순위 큐 방식을 쓴다고 적는다.^[16] 위 표의 복잡도는 원문에서 깨져 있어 복원했고, 선형 탐색의 O(V²)는 문맥으로만 복원한 값이다.^[16:1]
• 음수 간선이 있으면 그리디 전제가 깨지므로 Bellman-Ford를 써야 하고, Dijkstra는 음수 사이클도 탐지하지 못한다.^[4:2]

Bellman-Ford

• Bellman-Ford는 음수 가중치가 있는 그래프에서 단일 출발점 최단 경로를 구하고, 음수 사이클을 탐지한다.^[17]
• 전제는 "정점이 V개일 때 최단 경로는 최대 V-1개의 간선으로 이루어진다"는 것이다. 사이클이 없는 최단 경로는 같은 정점을 두 번 지날 이유가 없으므로 간선 수가 최대 V-1이고, 따라서 모든 간선을 V-1번 반복 확인하면 최단 거리가 수렴한다.^[18]
• 출발 노드 거리를 0, 나머지를 ∞로 둔 뒤 모든 간선을 확인하며 거리를 갱신하는 일을 V-1번 반복한다. V번째에도 갱신이 일어나면 음수 사이클이 있다.^[19]

int[] dist = new int[V + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;

// V-1번 반복: 모든 간선 완화
for (int i = 1; i < V; i++) {
    for (int[] edge : edges) { // edge = {from, to, weight}
        int from = edge[0], to = edge[1], w = edge[2];
        if (dist[from] != Integer.MAX_VALUE && dist[from] + w < dist[to]) {
            dist[to] = dist[from] + w;
        }
    }
}

// V번째 반복: 음수 사이클 탐지
boolean hasNegativeCycle = false;
for (int[] edge : edges) {
    int from = edge[0], to = edge[1], w = edge[2];
    if (dist[from] != Integer.MAX_VALUE && dist[from] + w < dist[to]) {
        hasNegativeCycle = true;
        break;
    }
}

• V-1번 반복한 뒤에는 최단 경로가 이미 수렴해 있어야 한다. 그런데 V번째 반복에서 또 갱신된다면 경로가 수렴하지 않고 계속 줄어든다는 뜻이므로 음수 사이클이 있다.^[19:1]
• 코드는 아직 도달하지 못한 정점(Integer.MAX_VALUE)에서 출발하는 간선을 건너뛴다.^[11:1] 이 검사가 없으면 Integer.MAX_VALUE에 양수 가중치를 더할 때 int 범위를 넘을 수 있다고 볼 수 있다. 이 이유는 이 Wiki의 해석이다.
• 시간 복잡도는 O(VE)로 Dijkstra보다 느리므로, 음수 간선이 없으면 Dijkstra를 고른다.^[7:1]

Floyd-Warshall

• Floyd-Warshall은 모든 정점 쌍 사이의 최단 경로를 구하는 DP 알고리즘이다.^[9:1]
• 전제는 "중간 경유 노드 k를 거쳐 갈 때 더 짧아지는가?"라는 질문이다. 경유할 수 있는 정점 집합을 {1, 2, …, k}로 점점 넓혀 가며 최단 경로를 확장하고, 모든 k에 대해 갱신을 마치면 전체 최단 경로가 완성된다.^[20]
• 점화식은 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])이고, k는 현재 경유할 수 있는 중간 노드다.^[21]
• 2차원 배열을 자기 자신까지는 0, 간선이 있으면 그 가중치, 없으면 ∞로 초기화한 뒤, 모든 노드 k를 차례로 경유 노드로 삼아 모든 (i, j) 쌍에 점화식을 적용한다.^[12:1] 원문의 초기화 설명은 기호가 깨져 있어 같은 노트의 코드로 복원했다.
• INF는 Integer.MAX_VALUE / 2로 두어 덧셈 오버플로를 막는다.^[12:2]

final int INF = Integer.MAX_VALUE / 2; // 오버플로 방지
int[][] dist = new int[V + 1][V + 1];

// 초기화
for (int i = 1; i <= V; i++)
    Arrays.fill(dist[i], INF);
for (int i = 1; i <= V; i++)
    dist[i][i] = 0;

// 간선 입력
for (int[] edge : edges)
    dist[edge[0]][edge[1]] = edge[2]; // 단방향

// 플로이드-워셜
for (int k = 1; k <= V; k++)
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= V; j++)
            if (dist[i][k] != INF && dist[k][j] != INF)
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

• 간선 입력은 단방향이고, 같은 (from, to) 간선이 여러 번 들어오면 마지막 값으로 덮어쓴다.^[12:3] 더 작은 가중치를 남기는 처리는 원문 코드에 없다. 이 판독은 이 Wiki가 코드를 읽고 덧붙인 것이다.

경로 복원

• 경로 자체가 필요하면 next[i][j](i에서 j로 가는 경로에서 i 다음 노드) 배열을 두고, k를 경유하도록 갱신할 때 next[i][j] = next[i][k]로 바꾼다.^[22]

int[][] next = new int[V + 1][V + 1]; // next[i][j]: i→j 경로의 i 다음 노드

// 초기화: 간선이 있으면 next[i][j] = j
for (int k = 1; k <= V; k++)
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= V; j++)
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
                next[i][j] = next[i][k]; // k를 경유하므로 i의 다음은 i→k의 다음
            }

// 경로 출력
List<Integer> getPath(int s, int t) {
    List<Integer> path = new ArrayList<>();
    path.add(s);
    while (s != t) {
        s = next[s][t];
        path.add(s);
    }
    return path;
}

• 이 코드를 그대로 쓰기 전에 확인할 점이 세 가지 있다. 이 세 가지는 이 Wiki가 코드를 읽고 덧붙인 것이다.^[22:1]
  • next 초기화(간선이 있으면 next[i][j] = j)는 주석으로만 적혀 있고 코드가 없다.
  • 본 루프와 달리 이 루프에는 INF 검사가 없다. INF를 Integer.MAX_VALUE / 2로 두었으므로 INF끼리 더해도 int 범위는 넘지 않는다. 다만 음수 간선이 있으면 INF에 음수를 더한 값이 INF보다 작아져, 경로가 없는 쌍이 갱신된 것처럼 보일 수 있다.
  • getPath는 s에서 t로 가는 경로가 없는 경우를 처리하지 않는다.

음수 사이클과 복잡도

• 음수 가중치 간선은 허용한다. 알고리즘을 수행한 뒤 dist[i][i] < 0인 정점이 있으면 음수 사이클이 있다.^[5:1] 원문은 이 조건의 dist가 깨져 있어 복원했다.

• 위 표의 시간 복잡도는 hub 노트 표기로 복원했다. 공간 복잡도 O(V²)와 "V ≤ 500"은 깨진 원문을 문맥으로만 복원한 값이다.^[23]
• Implementation Problem Approach의 허용 복잡도 표는 "1억 연산 ≈ 1초"를 기준으로 O(N³)을 N ≤ 100까지로 본다.^[24] 같은 기준으로 계산하면 500³은 1.25억 연산이다. 그래서 구현 표는 보수적인 하한이고 Floyd-Warshall 노트의 500은 경계값에 가깝다고 읽을 수 있다. 두 값은 모두 어림 규칙이다. 이 비교와 계산은 이 Wiki의 해석이다.

관련

• Graph Algorithms: 같은 "최소 비용 문제"의 다른 갈래인 MST와, 우선순위 큐·큐를 쓰는 다른 그래프 알고리즘을 다룬다.
• Algorithm Design Strategies: Dijkstra가 그리디, Bellman-Ford와 Floyd-Warshall이 DP로 분류되는 기준인 그리디와 DP의 적용 조건을 다룬다.
• Implementation Problem Approach: 정점 수로 허용 복잡도를 가늠하는 표와, Dijkstra가 쓰는 Java PriorityQueue 선택을 다룬다.

테스트 질문

• 음수 간선이 있는 단일 출발 최단 경로 문제에서 음수 사이클이 있는지도 알아야 한다면 무엇을 쓰고, 사이클은 어떻게 판별하는가?
• Dijkstra 구현에서 큐에서 꺼낸 비용이 기록된 거리보다 크면 건너뛰는 이유는 무엇인가?
• Floyd-Warshall을 수행한 뒤 음수 사이클은 어떻게 확인하는가?

출처