8. 최단 경로 탐색: 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 최단 경로 탐색 알고리즘중 가장 대표적인 알고리즘이라고 할 수 있습니다. 일반적으로 최단 경로 탐색 알고리즘 교육에서는 가장 첫 장으로 소개되기 마련이며, 최단 경로 탐색 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 중에서 가장 시간복잡도가 낮습니다. 하지만 모든 최단 경로 탐색 문제에 다익스트라 알고리즘을 사용할 수 있는 것은 아닙니다. 다익스트라 알고리즘의 위키백과 정의를 살펴보겠습니다.

컴퓨터 과학에서, 데이크스트라 알고리즘(=다익스트라 알고리즘)(영어: Dijkstra algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라의 이름에서 유래했다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.

위키백과: 데이크스트라 알고리즘

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

위 정의에서 주의해서 보아야할 부분은 다익스트라가 알고리즘으로 답을 구할 수 있는 그래프는 음수 가중치를 갖지 않는 유향 그래프라는 것입니다. 음수 가중치를 갖는 경우는 벨만-포드 알고리즘을 이용합니다. 구제적으로 문제에서 주어진 간선 정보에 음수값이 있거나 시간을 거슬를 수 있다고 하거나 비용이 감소한다는 정보가 있다면 벨만-포드 알고리즘을 이용해서 풀어야 합니다.

다익스트라 알고리즘 문제는 다른 그래프 문제들과 마찬가지로 노드 정보와 간선 정보가 주어집니다. 일반적으로 노드는 Vertex(꼭지점), 간선은 Edge(선)라고 표현되는 경우가 많습니다. 그래서 문제에서도 노드정보는 V로 간선정보는 E로 표현합니다. 주어진 정보를 이용하여 그래프 구조를 구현합니다. 일반적으로 Array와 List를 이용하여 구현합니다. 그리고 시작 노드에서 다른 노드로 가기 위한 최소 비용을 저장해줄 전체 노드 개수 만큼의 일차원 배열을 하나 선언하도록 합니다. 시작점에서 다른 노드까지 가는 비용은 계산되지 않았으므로 무한대 값을 넣어줍니다. 무한대 값을 세팅하는 것은 알고리즘이 작동하기 전에는 시작 노드에서 다른 노드로 이동할 수 있는지 알 수 없기 때문에 도달할 수 있는 방법이 없다는 의미를 담고 있습니다. 일반적으로 무한대 값으로 Integer.MAX_VALUE로 int 최대값을 세팅하는 경우가 많습니다. 개인적으로 Integer.MAX_VALUE를 별로 좋아하지 않는데 Integer.MAX_VALUE는 int 최대값이므로 1이라도 더하게 되면 overflow가 되서 음수 값이로 바뀌어 버리기 때문입니다. 그러므로 무한대 값을 연산중에 나올 수 없는 적당한 최대값으로 세팅하면 이러한 문제를 사전에 방지할 수 있습니다.  탐색 시작과 함께 시작점은 비용이 0으로 세팅됩니다. 시작 노드는 시작과 동시에 도착하는 것과 마찬가지입니다. 이제 시작 노드에서 연결된 간선을 확인하면서 그 간선으로 가는 비용을 업데이트 해줍니다. 탐색된 노드들은 시작노드에서 이동할 수 있는 방법이 있다는 것이 증명된 노드인 동시에 얼마의 비용을 치르고 이동할 수 있는지를 의미하는 비용 정보를 갖게된 노드입니다. 노드들은 다른 노드로 연결될 수 있고 또한 더 작은 비용으로 다른 노드들을 연결해줄 수 있는 후보 노드들이 되므로 노드 정보를 우선순위 큐(Priority Queue)에 저장해줍니다. 우선순위 큐에 담겨있는 노드들은 비용이 낮은 순서대로 정렬되어 있기 때문에, 상대적으로 더 적은 비용을 가진 노드 정보들이 먼저 연산되도록 유도됩니다.

위키백과: 우선순위 큐(Priority Queue)

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

이제 Queue에는 시작 노드에서 탐색을 마친 노드들이 담겨 있습니다. 그리고 그 노드들은 시작 노드에서 다른 노드들로 넘어가기 위한 징검다리가 됩니다. Queue에는 시작 노드에서 해당 노드까지 가는데 드는 비용을 포함하고 있으므로 이 비용 정보를 이용하여 다른 노드로 이동하는 비용을 더 줄일 수 있는지 확인해볼 수 있습니다. 만일 Queue에서 나온 노드를 이용하여 다른 노드로 이동하는 비용을 더 줄일 수 있다면 최소비용 정보를 저장한 배열 내 값을 갱신합니다. 그리고 비용이 갱신되었다는 것은 기존에는 발견되지 않았던 더 적은 비용의 새로운 루트가 발견되었다는 뜻이므로 그 노드 정보를 Queue에 추가시킵니다. Queue가 빌 때까지 이 작업이 이루어지면 시작 노드에서 각 노드에 도달하는데 필요한 최소비용이 배열에 저장되게 됩니다.

문제를 풀어보면서 이해해보시기 바랍니다.

1916번: 최소비용 구하기 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Main {
    private static ArrayList<Integer>[] con;
    private static ArrayList<Integer>[] conv;
    static int[] D;
    private static int n;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        n = Integer.parseInt(br.readLine().trim());
        int m = Integer.parseInt(br.readLine().trim());
 
        con = new ArrayList[n + 1];
        conv = new ArrayList[n + 1];
 
        for (int i = 1; i <= n; i++) {
            con[i] = new ArrayList<>();
            conv[i] = new ArrayList<>();
        }
 
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine().trim());
 
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
            con[a].add(b);
            conv[a].add(c);
        }
 
        st = new StringTokenizer(br.readLine().trim());
 
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
 
        System.out.println(dijkstra(s, e));
    }
 
    private static int dijkstra(int a, int b) {
        D = new int[n + 1];
        for (int i = 1; i <= n; i++)
            D[i] = Integer.MAX_VALUE;
 
        PriorityQueue<int[]> que = new PriorityQueue<>(10, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
 
        D[a] = 0;
        que.add(new int[] { 0, a });
        while (!que.isEmpty()) {
            int q = que.peek()[1];
            int d = que.peek()[0];
            que.poll();
            if (D[q] != d)
                continue;
            for (int i = 0; i < con[q].size(); i++) {
                int j = con[q].get(i);
                int v = conv[q].get(i);
                if (D[j] > D[q] + v) {
                    D[j] = D[q] + v;
                    que.add(new int[] { D[j], j });
                }
            }
        }
        return D[b];
    }
}