[알고리즘] 다익스트라 알고리즘 (Dijkstra)

다익스트라(Dijkstra) 알고리즘에 대해 공부 후 정리하였습니다.

다익스트라 알고리즘

1️⃣ 개념

가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
BFS의 가중치 버전이라고 생각 가능 (BFS는 모든 간선 가중치가 1일 때 다익스트라와 동일)

2️⃣ 특징

• Greedy + DP 성격을 동시에 가짐
• 각 단계에서 가장 가까운 정점을 선택하고, 그 경로를 확정
• 선택된 최단 거리를 기반으로 다른 거리 갱신
• 음수 가중치 불가 (음수 간선이 있으면 벨만-포드 사용)
• 우선순위 큐를 쓰면 O(E log V)에 동작
• 모든 정점의 최단 거리를 한 번에 구할 수 있음

3️⃣ 시간 복잡도

구현 방식	자료구조	시간 복잡도
기본 배열	배열	O(V²)
개선	PriorityQueue(최소 힙)	O(E log V)

• V: 정점 개수 / E: 간선 개수
• E log V 방식이 대부분의 경우 빠름 (희소 그래프일 때 유리)

4️⃣ 구현 방법

1. 시작 정점의 거리를 0으로 설정, 나머지는 무한대
2. 방문하지 않은 정점 중 거리가 가장 짧은 정점 선택
3. 선택한 정점을 거쳐가는 경로로 다른 정점 거리 갱신
4. 모든 정점이 처리될 때까지 반복

5️⃣ 기본 코드 (PriorityQueue 사용)

import java.util.*;

class Node implements Comparable<Node> {
    int vertex, cost;
    public Node(int vertex, int cost) {
        this.vertex = vertex;
        this.cost = cost;
    }
    public int compareTo(Node o) {
        return this.cost - o.cost; // 최소 힙
    }
}

public class DijkstraExample {
    static final int INF = Integer.MAX_VALUE;
    static List<List<Node>> graph = new ArrayList<>();
    static int[] dist;

    public static void main(String[] args) {
        int V = 5; // 정점 개수
        int E = 6; // 간선 개수
        dist = new int[V + 1];

        // 그래프 초기화
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        // 예시 간선 (양방향)
        addEdge(1, 2, 2);
        addEdge(1, 3, 5);
        addEdge(2, 3, 1);
        addEdge(2, 4, 2);
        addEdge(3, 4, 3);
        addEdge(4, 5, 1);

        dijkstra(1);

        for (int i = 1; i <= V; i++) {
            System.out.println("1 → " + i + " 최단 거리: " + (dist[i] == INF ? "INF" : dist[i]));
        }
    }

    static void addEdge(int u, int v, int w) {
        graph.get(u).add(new Node(v, w));
        graph.get(v).add(new Node(u, w)); // 양방향이면 필요
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(dist, INF);
        dist[start] = 0;
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            int cur = now.vertex;
            int curCost = now.cost;

            // 이미 처리된 거리보다 크면 무시
            if (curCost > dist[cur]) continue;

            for (Node next : graph.get(cur)) {
                int newDist = dist[cur] + next.cost;
                if (newDist < dist[next.vertex]) {
                    dist[next.vertex] = newDist;
                    pq.offer(new Node(next.vertex, newDist));
                }
            }
        }
    }
}