다익스트라 알고리즘 (Dijkstra’s Algorithm) 개념 정리

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

• 최단 경로(Shortest Path) 알고리즘 중 하나.
• 특정 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
• 음수 가중치가 없을 때만 사용 가능.

2. 원리 (Greedy + Priority Queue)

• 매번 가장 가까운 정점을 선택해 확정(visited)한다.
• 해당 정점을 거쳐 다른 정점으로 가는 경로를 최단 거리로 갱신한다.
• 이를 반복하면서 모든 정점의 최단 거리를 구한다.

핵심 아이디어:

"가장 가까운 정점부터 처리하면, 그 이후에는 더 짧은 경로가 나올 수 없다."

3. 알고리즘 과정

1. 시작 정점의 거리를 0으로, 나머지는 ∞(무한대)로 초기화.
2. 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택.
3. 선택한 정점을 거쳐 갈 수 있는 이웃 정점들의 거리를 갱신.
4. 모든 정점을 방문할 때까지 2~3을 반복.

4. 구현 (Java / Python 예시)

Java (우선순위 큐 이용)

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 other) {
        return this.cost - other.cost;
    }
}

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

    public static void dijkstra(int start, int n) {
        dist = new int[n+1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

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

            if (dist[now] < cost) continue;

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

    public static void main(String[] args) {
        int n = 5; // 정점 개수
        int start = 1; // 시작 정점

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

        // 간선 추가 (양방향 or 단방향 상황에 맞게)
        graph.get(1).add(new Node(2, 2));
        graph.get(1).add(new Node(3, 5));
        graph.get(2).add(new Node(3, 1));
        graph.get(2).add(new Node(4, 2));
        graph.get(3).add(new Node(4, 3));
        graph.get(3).add(new Node(5, 1));
        graph.get(4).add(new Node(5, 2));

        // 다익스트라 실행
        dijkstra(start, n);

        // 결과 출력
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) System.out.println(i + "까지의 거리: INF");
            else System.out.println(i + "까지의 거리: " + dist[i]);
        }
    }
}

6. 시간 복잡도

• 인접 리스트 + 우선순위 큐 사용: O(E log V)
• (E = 간선 수, V = 정점 수)

7. 활용 포인트

• 실생활: 지도 앱, 네트워크 라우팅
• 알고리즘 문제: 최단 경로 유형, 최소 비용 문제
• 주의: 음수 간선이 있으면 벨만-포드(Bellman-Ford) 사용해야 함