다익스트라

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

다익스트라 알고리즘은 가중치가 있는 그래프에서 하나의 시작점 → 모든 노드까지의 최단 거리를 구하는 알고리즘
(특정 도착점 하나만 필요해도 같은 원리를 적용)

특징

• 음수 가중치가 없는 그래프에서만 사용 가능
• BFS + 우선순위 큐(Heap) 개념이 결합된 형태
• 시간 복잡도: O(E log V) (E = 간선 수, V = 노드 수)

2. 동작 원리

1. 모든 노드의 거리를 무한대(∞) 로 초기화, 시작 노드는 0으로 설정
2. 아직 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택
3. 해당 노드와 연결된 다른 노드의 거리를 더 작은 값으로 갱신
4. 2~3 과정을 모든 노드가 처리될 때까지 반복

3. 간단 예시

예를 들어 A → H까지의 최단 거리를 구한다고 하면 다음과 같은 순서로 진행된다.

1. 시작점 A의 거리를 0으로, 나머지는 ∞로 초기화
2. 가장 가까운 노드 선택 → 거리 갱신
3. 모든 노드가 처리될 때까지 반복
   → 마지막에 남은 값이 시작점으로부터의 최단 거리

4. 자바 코드 구현

그래프 표현

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

Map<Integer, List<Edge>> graph = new HashMap<>() {{
    put(1, List.of(new Edge(2, 2), new Edge(4, 1)));
    put(2, List.of(new Edge(3, 2), new Edge(5, 2), new Edge(6, 4)));
    put(3, List.of(new Edge(6, 4)));
    put(4, List.of(new Edge(7, 5)));
    put(5, List.of(new Edge(8, 1)));
    put(6, List.of(new Edge(5, 3)));
    put(7, List.of(new Edge(6, 7), new Edge(8, 6)));
    put(8, List.of());
}};

다익스트라 함수

static class Node implements Comparable<Node> {
    int index, distance;
    Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }
    public int compareTo(Node o) {
        return Integer.compare(this.distance, o.distance);
    }
}

static int dijkstra(Map<Integer, List<Edge>> graph, int start, int end) {
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[graph.size() + 1];
    Arrays.fill(dist, INF);
    dist[start] = 0;

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

    while (!pq.isEmpty()) {
        Node cur = pq.poll();
        if (dist[cur.index] < cur.distance) continue;

        for (Edge edge : graph.get(cur.index)) {
            int newDist = dist[cur.index] + edge.weight;
            if (newDist < dist[edge.to]) {
                dist[edge.to] = newDist;
                pq.add(new Node(edge.to, newDist));
            }
        }
    }
    return dist[end];
}

실행 예시

public static void main(String[] args) {
    int distance = dijkstra(graph, 1, 8);
    System.out.println("1번에서 8번까지 최단 거리: " + distance);
}