[JAVA] 다익스트라 (Dijkstra) (+ Priority Queue을 사용한 시간 단축)

Dijkstra 란?

• 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘
  • 단, 가중치에 음수가 있으면 사용할 수 없음
• 시간복잡도 : O(E logN) (N:노드의 수, E: 간선의 수)

• 다음과 같은 그래프가 있다고 가정
• 1번 노드에서 2, 3, 4, 5번 노드까지의 최단거리를 모두 구해야 함
• dist[1~5] = [0, ∞, ∞, ∞, ∞]로 초기화 후 시작
• 1번 노드에서 갈 수 있는 노드 = 2, 3, 4
• 1(시작노드) -> 2로 갈 때 드는 비용 ( = dist[1] + (1->2) )과 지금까지 2로가는 최소 비용 (=dist[2])를 비교해서 지금까지 2로가는 최소비용이 더 크다면 dist[2] = dist[1] + (1->2)로 갱신
• 이 방식으로 1번노드에서 갈 수 있는 노드들에 대한 비교를 마치면, dist = [0, 1, 2, 6, ∞]
• 1번 노드를 제외하고, 남은 것중 dist값이 가장 작은 노드 = 2
• 2번 노드는 이제 최단 거리가 확정됨
• 2번 노드에서 갈 수 있는 노드 = 4, 5
• dist[4]와 dist[2] + (2->4)를 비교했을 때, dist[4]가 더 큼
  • 이 뜻은 지금까지 4번 노드로 가는 방법보다, 2번 노드를 경유해 4번 노드로 가는 방법이 더 좋다는 뜻 => 값 갱신
• 이 방식으로 2번노드에서 갈 수 있는 노드들에 대한 비교를 마치면, dist = [0, 1, 2, 5, 16]
• 1, 2번 노드를 제외하고, 남은 것 중 dist값이 가장 작은 노드 = 3
• 3번 노드 최단 거리 확정
• 3번 노드에서의 비교를 마치면, dist = [0, 1, 2, 4, 16]
• 4번 노드에서의 비교를 마치면, dist = [0, 1, 2, 4, 12]
• 5번 노드에서의 비교를 마치면, dist = [0, 1, 2, 4, 12]
• 1번 노드에서 1, 2, 3, 4, 5번 노드로 가는데 걸리는 최소 비용 = 0, 1, 2, 4, 12

시간복잡도 계산 (Priority Queue를 이용한 시간 줄이기)

• N : 노드의 수, E : 간선의 수 라고 했을때, 이 알고리즘의 시간복잡도를 계산

1. 현재 노드에서 갈 수 있는 노드 중 가장 작은 dist 값을 가진 노드를 찾기 위해서는 최악의 경우 O(N)의 시간이 걸림
2. 모든 노드들을 한 번씩 들려야 되므로 O(N)이 걸림

• 따라서 시간복잡도는 O(N^2)
• Priority Queue(우선순위 큐)를 사용하면 시간을 줄일 수 있음 => Priority Queue에서 삽입, 삭제의 시간 복잡도는 O(log N)
• Priority Queue를 사용해 현재 가장 작은 dist를 가진 노드를 찾는다면 O(log N)의 시간이 걸림
• 이런식으로 다음 노드를 구한다면 이 노드에서 다음 노드까지의 dist를 계산해야 함
  • 이 작업이 최악의 경우 모든 간선을 확인해야 되기 때문에 O(E)의 시간이 걸림
• 따라서 시간복잡도는 O(E logN)

구현

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

이 문제를 다익스트라를 통해 해결하면서 구현해봄

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class p1753 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());

        ArrayList<Node>[] connections = new ArrayList[n + 1];
        for(int i = 1 ; i <= n ; i ++) {
            connections[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < e ; i ++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            connections[x].add(new Node(y, z));
        }
        /*
            입력          =>      connections
            5 6                  [1] = { (2,2), (3,3) }
            1                    [2] = { (3,4), (4,5) }
            5 1 1                [3] = { (4,6) }
            1 2 2                [4] = {}
            1 3 3                [5] = { (1,1) }
            2 3 4
            2 4 5
            3 4 6
        */

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        boolean[] visited = new boolean[n + 1];

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

        while(!pq.isEmpty()) {
            PqFormat now = pq.poll();
            if(visited[now.index] == true) continue;

            visited[now.index] = true;
            for(Node node : connections[now.index]) {
                // now.index : 현재 노드 번호    now.dist : 현재 노드의 dist
                // node.next : 현재 노드와 연결된 다음 노드 번호
                // node.cost : 현재 노드에서 다음 노드까지 가는데의 비용

                // dist[다음노드] > dist[현재노드] + 현재노드에서 다음노드 가는 비용이면 갱신
                if(dist[node.next] > dist[now.index] + node.cost) {
                    dist[node.next] = dist[now.index] + node.cost;
                    pq.add(new PqFormat(node.next, dist[node.next]));
                }
            }
        }

        for(int i = 1 ; i <= n ; i ++) {
            if(dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }
        }
    }
    static class Node {
        int next, cost;
        public Node(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }

    static class PqFormat implements Comparable<PqFormat>{
        int index, dist;
        PqFormat(int index, int dist) {
            this.index = index;
            this.dist = dist;
        }

        @Override
        public int compareTo(PqFormat o) {
            // dist 기준 오름차순 정렬
            return this.dist - o.dist;
        }
    }
}