이번에는 다익스트라에 대해 정리하고, 문제를 기준으로 이해해보자.

위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

다익스트라 알고리즘?

다익스트라는 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.

다익스트라는 2중 for문을 이용한 방법, 우선순위 큐를 이용한 탐색으로 구현 방법이 나뉜다.

그럼 이번에도 그림으로 표현해보도록 하겠다.

이전 글인 플로이드 워셜과 유사하게 접근이 가능하다.

INF를 사용하지만 이번에는 시작 지점만을 위한 가중치 배열인 dist를 따로 선언하여 사용한다.

처음에는 dist 배열 내에서 시작 지점인 자신을 제외한 모든 노드를 향한 가중치를 INF로 두고 업데이트해나가며 다른 모든 노드까지의 최단거리를 구해낼 수 있다.

구현 - 우선 순위 큐

먼저 위에서 그림으로 표현한 인접리스트 방식으로 설명하겠다.

private static class Node implements Comparable<Node>{ // Comparable 구현
    public int num;
    public int weight;

    public Node(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

private static void dijkstra(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(start, 0)); // start 지점 등록
    dist[start] = 0; // 자기 자신이므로 가중치 0으로 변경
    boolean[] visited = new boolean[N+1];

    while (!pq.isEmpty()) {
        Node current = pq.poll();
        int currentNum = current.num;

        if (visited[currentNum]) continue;

        visited[currentNum] = true;
        for (Node node : list[currentNum]) {
            if (dist[node.num] > dist[currentNum] + node.weight) { // dist에 기록되어 있는 인접 노드의 가중치 보다 현재 노드의 가중치 + 인접 노드의 가중치가 적다면
                dist[node.num] = dist[currentNum] + node.weight; // 갱신
                pq.add(new Node(node.num, dist[node.num])); // 우선 순위 큐에 갱신 된 노드를 추가
            }
        }
    }
}