다익스트라

1. 다익스트라 알고리즘이란?

다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디(Greedy) 알고리즘을 바탕으로 하는 최단 경로 탐색 알고리즘입니다. 특정한 하나의 정점(시작점)에서 그래프 내의 다른 모든 정점까지의 최단 거리를 구하는 '단일 출발점 최단 경로(Single-source Shortest Path)' 문제를 해결하는 데 사용됩니다.

핵심 원리는 "현재까지 알고 있는 최단 경로를 바탕으로, 아직 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택해 인접한 노드들의 최단 거리를 계속해서 갱신해 나가는 것"입니다. 한 번 최단 거리가 확정된 노드는 다시 처리하지 않기 때문에 매 단계마다 탐색 범위가 줄어듭니다.

2. 알고리즘의 한계점

• 음수 가중치(Negative Weight) 처리 불가: 다익스트라 알고리즘은 '지금까지 계산된 최단 거리는 더 이상 짧아지지 않는다'는 그리디적 가정을 기반으로 동작합니다. 따라서 간선의 가중치에 음수가 포함되어 있으면 이 가정이 깨져 올바른 최단 경로를 찾지 못할 수 있습니다. (음수 가중치가 존재하는 그래프의 최단 경로를 구하려면 '벨만-포드(Bellman-Ford) 알고리즘'을 사용해야 합니다.)

3. 구현 방법 1: 순차 탐색

매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 찾기 위해 전체 노드 배열을 순차 탐색하는 직관적인 방법입니다.

• 시간 복잡도: O(V^2) (V는 노드의 개수)
• 특징: 노드의 개수가 적고 간선이 매우 많은 밀집 그래프(Dense Graph)에 적합합니다. 하지만 노드의 수가 10,000개를 넘어가는 일반적인 코딩 테스트 환경에서는 시간 초과가 발생할 수 있습니다.

import java.util.Arrays;

public class DijkstraNaive {
    // V: 정점의 개수, graph: 인접 행렬 형태의 그래프 가중치 정보
    public static int[] dijkstra(int start, int V, int[][] graph) {
        boolean[] visited = new boolean[V + 1];
        int[] dist = new int[V + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        dist[start] = 0; // 시작점의 거리는 0

        for (int i = 0; i < V - 1; i++) {
            // 1. 아직 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 찾기
            int minDist = Integer.MAX_VALUE;
            int minIdx = 0;
            for (int j = 1; j <= V; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minIdx = j;
                }
            }

            // 2. 해당 노드 방문 처리
            visited[minIdx] = true;

            // 3. 선택된 노드를 거쳐가는 인접 노드들의 최단 거리 갱신
            for (int j = 1; j <= V; j++) {
                // 연결되어 있고, 방문하지 않았으며, 기존 거리보다 거쳐가는 것이 더 짧은 경우
                if (!visited[j] && graph[minIdx][j] != 0 && dist[minIdx] != Integer.MAX_VALUE) {
                    if (dist[minIdx] + graph[minIdx][j] < dist[j]) {
                        dist[j] = dist[minIdx] + graph[minIdx][j];
                    }
                }
            }
        }
        
        return dist;
    }
}

5. 구현 방법 2: 우선순위 큐(Priority Queue)를 활용한 접근법

순차 탐색의 O(V) 비용을 줄이기 위해, 가장 거리가 짧은 노드를 O(\log V) 만에 찾아주는 최소 힙(Min-Heap) 구조의 우선순위 큐를 사용하는 정석적인 방법입니다.

• 시간 복잡도: O(E \log V) (E는 간선의 개수, V는 노드의 개수)
• 특징: 정점의 개수가 많고 상대적으로 간선의 개수가 적은 희소 그래프(Sparse Graph)에서 압도적인 성능을 보입니다. 실전 코딩 테스트에서는 대부분 이 방식으로 다익스트라를 구현해야 합니다.

import java.util.*;

public class DijkstraPQ {
    static class Node {
        int v, w;
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    // V: 정점의 개수, adj: 인접 리스트 형태의 그래프 정보
    public static int[] dijkstra(int start, int V, List<Node>[] adj) {
        int[] dist = new int[V + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        // 누적 거리를 기준으로 오름차순 정렬하는 우선순위 큐
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.w, n2.w));

        // 시작점 설정
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            // 1. 가장 누적 거리가 짧은 노드 추출
            Node cur = pq.poll();

            // 2. 이미 갱신되어 더 짧은 경로가 있다면 무시 (방문 체크 역할)
            if (dist[cur.v] < cur.w) {
                continue;
            }

            // 3. 인접 노드들을 확인하며 최단 거리 갱신
            for (Node next : adj[cur.v]) {
                // (현재 노드까지의 최단 거리 + 인접 노드로 가는 가중치)가 기존 거리보다 작을 경우
                if (dist[next.v] > cur.w + next.w) {
                    dist[next.v] = cur.w + next.w;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }
        }

        return dist;
    }
}