데이크스트라, 다익스트라 (dijkstra) 알고리즘

데이크스트라 알고리즘은 최단 경로 문제를 풀 때 사용된다. 같은 유형인 벨만-포드 알고리즘과 비슷한 방식으로 구현되지만, 둘은 전제조건에서 큰 차이가 있다.

벨만-포드 알고리즘은 음의 간선이 있으며, 음의 유향 사이클이 존재할 수 있다. 

데이크스트라 알고리즘은 간선이 항상 양의 값을 가지며 사이클이 존재하지 않는다. 

 

데이크스트라 알고리즘은 일반적으로 단순 구현 방법과 개선된 구현 방법이 존재한다. 

단순 구현 방법의 경우 2중 for문을 이용하기 때문에 O(n^)의 복잡도이다. 그렇기 때문에 이를 개선하여 O(ElogV) 의 복잡도인 데이크스트라 구현 방법을 주로 사용한다.   

 

개선된 데이크스트라 알고리즘의 동작 방식을 알아보자.

우선, 최단경로를 저장할 d[] 배열이 존재해야 한다. 데이크스트라 알고리즘은 다이나믹 프로그래밍 기법인 '완화' 를 이용하여 최단 경로를 구한다. 그렇기 때문에 d[] 배열은 더 작은 값으로 갱신되기를 반복하게 된다. 

또한, 유향 그래프이며 간선이 항상 양의 값을 가지는 데이크스트라 알고리즘은 방문 순서에 대한 고민 없이 가장 비용이 적게 드는 방향으로 완화를 수행하면 되기 때문에 벨만-포드 알고리즘처럼 2중 for문이 강제되지 않는다. 

최소 비용을 가지는 노드 부터 방문하기 위해서 우선순위 큐에 노드와 간선 정보를 저장한다. 

 

 시작 노드에 대한 정보를 큐에 삽입한 후 이 큐에 원소가 있는 동안 아래의 행위를 반복한다.

1. 우선순위 큐에서 노드 하나를 꺼낸다.

2. 해당 노드가 최단 거리로 갱신된 노드인지 확인한다.

3. 꺼낸 노드와 연결되어 있는 노드를 하나씩 방문하며 해당 노드가 가지는 최단 거리 값과, 꺼낸 노드에서 연결 노드로 가는 비용 + 꺼낸 노드까지의 최단 비용 을 비교하여, 더 작은 수를 d 배열에 덮어씌운다.

4. d 배열에 대해 갱신이 일어난다면 queue에 해당 노드의 정보를 저장한다. 

 

예제

왼쪽은 그래프의 연결 정보, 오른쪽 위는 최단 경로를 저장할 d 배열, 아래는 우선순위 큐이다.

 

 먼저 시작할 노드의 정보를 priority queue에 저장한다. 그리고 시작점 노드의 거리는 0이다. 

1번 노드와 연결되어 있는 2번, 3번, 4번 노드에 대하여 d 배열의 값과 cost(1번노드의 최단 거리 + 1->2(or 3, or 4)번으로 가는데 필요한 거리 비용) 를 비교하여 cost가 더 작다면 d 배열을 갱신한다. 현재까지는 2,3,4번 값이 전부 INF (무한대) 이기 때문에 무조건 cost로의 갱신이 일어난다. 갱신 후에는 우선순위 큐에 해당 노드의 정보(노드 인덱스, 최단거리 값) 를 넣어준다. 

 

위의 수행이 끝나면 1번 노드의 최단 거리 구하기는 끝이 나게 되고, 다시 우선순위 큐에서 노드 하나를 꺼내 온다.

우선순위 큐에서 2번 노드에 대한 정보를 꺼냈다. 2번 노드와 연결되어 있는 것은 3번 노드이므로 d[3] 값과 d[2] + 2->3 거리비용 값인 cost를 비교한다.  cost가 더 작은 값이기 때문에, d[3] 에 대한 갱신이 일어나고 3번 노드의 정보가 큐에 삽입된다. 

 2번 노드에 대한 처리가 끝났다. 큐에서 노드를 꺼내온다.

3번 노드는 4번 노드와 연결되어 있다. 4번 노드의 최단 거리 값인 d[4]와 현재 노드인 3번의 최단 거리 + 3->4 거리 비용 (cost) 중 어떤 것이 더 작은지 비교한다. d[4]는 7, 3번의 최단거리인 2 + (3->4) 비용은 2 = 4이기 때문에 cost가 더 작은 값으로 d[4] 에 대한 갱신이 일어난다. 그리고 큐에 4번 노드에 대한 정보가 저장된다. 

 

 

3번 노드에 대한 처리가 끝났다. 큐에서 노드를 하나 더 꺼내온다. 

   그런데 꺼내 온 노드가 3번 노드에 대한 정보이다. 이전에 꺼냈던 Node(3,2) 가 3번 노드에 대한 최단 거리였기 때문에 지금 들어오는 Node(3,4) 즉, 최단 경로가 아닌 정보는 폐기한다. 

 

 큐에서 노드를 하나 더 꺼내온다. 4번 노드에 대한 정보이다.

4번 노드는 자신에게서 뻗어져 나가는 연결 노드가 없기 때문에 for문이 종료된다. 

 

큐에서 노드를 하나 더 꺼내온다.

이도 3번 노드와 마찬가지로 이미 최단 경로가 구해진 노드에 대한 정보이기 때문에 폐기한다.

 

큐에 더 이상 남은 것이 없기 때문에 최단 경로를 구하는 로직이 종료된다. 

1번 노드는 시작 노드이기 때문에 거리가 0,

2번 노드는 1->2로 거쳐가는 방법으로 거리가 1,

3번 노드는 1->2->3 으로 거쳐가는 방법으로 거리가 2,

4번 노드는 1->2->3->4 로 거쳐가는 방법으로 거리가 4이다.

 

전체 코드  

import java.util.*;

class Node implements Comparable<Node> {

    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public int getIndex() {
        return this.index;
    }

    public int getDistance() {
        return this.distance;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    //우선순위 큐에 Node 객체를 삽입할 것이기 때문에, 
    //해당 객체가 우선순위 큐에 어떻게 쌓일지 compareTo 를 구현해주어야함
    @Override
    public int compareTo(Node other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int n, m, start;
    // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    // 최단 거리 테이블 만들기
    public static int[] d = new int[100001];

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while(!pq.isEmpty()) { // 큐가 비어있지 않다면
            // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
            Node node = pq.poll();
            int dist = node.getDistance(); // 현재 노드까지의 비용
            int now = node.getIndex(); // 현재 노드
            // 현재 노드가 이미 처리된 적이 있는 노드라면 무시 (Node(3,4) , Node(4,7) 경우
            if (d[now] < dist) continue; //우선순위 큐에 두 개 이상의 노드 처리가 들어갈 수 있다. 그렇기 때문에 ...
            // 현재 노드와 연결된 다른 인접한 노드들을 확인
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).getDistance();
                // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                if (cost < d[graph.get(now).get(i).getIndex()]) {
                    d[graph.get(now).get(i).getIndex()] = cost;
                    pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

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

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
            graph.get(a).add(new Node(b, c));
        }

        // 최단 거리 테이블을 모두 무한으로 초기화
        Arrays.fill(d, INF);

        // 다익스트라 알고리즘을 수행
        dijkstra(start);

        // 모든 노드로 가기 위한 최단 거리를 출력
        for (int i = 1; i <= n; i++) {
            // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
            if (d[i] == INF) {
                System.out.println("INFINITY");
            }
            // 도달할 수 있는 경우 거리를 출력
            else {
                System.out.println(d[i]);
            }
        }
    }
}

코드는 이것이 취업을 위한 코딩 테스트다 with python- 저자 나동빈 책의 JAVA 코드를 참고했다.