[Algorithm] Dijkstra Algorithm이란?

개요

알고리즘을 사용할 때는 해당 알고리즘이 어떤 경우에 사용 되는 지에 대한 정확한 이해가 필요합니다. 이번 포스팅에서는 다익스트라 알고리즘과 개선된 다익스트라 알고리즘에 대해 알아보도록 하겠습니다.

최단 경로 알고리즘

다익스트라 (Dijkstra) 알고리즘은 최단 경로 탐색 (Shortest Path) 알고리즘 중 하나로, 특정 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 최단 경로 알고리즘에는 다익스트라 외에도 플로이드-와셜 (Floyd-Warshall) 알고리즘과 벨만-포드 (Bellman-Ford) 알고리즘이 있으며, 각 알고리즘은 다른 상황에서 사용됩니다.

다익스트라 알고리즘

다익스트라 알고리즘은 앞 전에 언급한 것 처럼 그래프에 여러 정점이 존재할 때, 특정 정점에서 출발하여 다른 모든 정점으로가는 각각의 최단 경로를 구해주는 알고리즘입니다. 다익스트라 알고리즘의 특징으로는 음의 간선, 즉 0보다 작은 값을 가지는 간선이 없어야 정상적으로 동작합니다.

동작 순서는 다음과 같습니다.

1. 시작 정점을 설정
2. 해당 시작 정점을 기준으로 최단거리 테이블을 초기화
3. 방문하지 않은 정점 중에서 최단 거리가 짧은 정점을 선택
4. 해당 정점을 거쳐 다른 정점으로 가는 비용 계산
5. 모든 정점을 방문할 때 까지 3,4 번 과정을 반복

(모든 간선의 가중치는 1이고, 시작 정점은 1이라고 가정합니다)

package baekjoon.graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class _18352 {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken()); 
        int X = Integer.parseInt(st.nextToken());

        // Initialization
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        boolean[] ch = new boolean[N + 1];
        int[] dist = new int[N + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[X] = 0;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
        }

        for (int i = 0; i < N; i++) {
            int index = shortestIndex(dist, ch);
            ch[index] = true;
            for (int j = 0; j < graph.get(index).size(); j++) {
                int next = graph.get(index).get(j);
                dist[next] = Math.min(dist[next], dist[index] + 1);
            }
        }
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == K) {
                sb.append(i + "\n");
            }
        }
        System.out.println(sb.length() == 0 ? -1 : sb);
    }

    public static int shortestIndex(int[] dist, boolean[] ch) {
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] < min && !ch[i]) {
                min = dist[i];
                index = i;
            }
        }
        return index;
    }
}

개선된 다익스트라 알고리즘

다익스트라 알고리즘에서 자료구조를 바꾼다면 성능을 개선할 수 있습니다. 바로 우선순위 큐를 사용하는 방법입니다.

기존의 다익스트라 모든 경우의 수를 다 계산하는 반면, 우선 순위 큐는 가중치의 합이 적은 노드들이 제일 앞에 배치되기 때문에 모든 경우의 수를 돌지 않더라도 최적의 최단 경로를 찾을 수 있습니다.

package baekjoon.graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _18352 {

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        // Initialization
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        boolean[] ch = new boolean[N + 1];
        int[] dist = new int[N + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[X] = 0;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b, 1));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.offer(new Node(X, 0));
            while (!pq.isEmpty()) {
                Node temp = pq.poll();
                int index = temp.node;
                if (ch[index]) {
                    continue;
                }
                ch[index] = true;
                for (Node n : graph.get(index)) {
                    if (!ch[n.node] && n.weight + dist[index] < dist[n.node]) {
                        dist[n.node] = n.weight + dist[index];
                        pq.offer(new Node(n.node, dist[n.node]));
                    }
                }
            }
        }
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == K) {
                sb.append(i + "\n");
            }
        }
        System.out.println(sb.length() == 0 ? -1 : sb);
    }

    static class Node implements Comparable<Node> {

        int node;
        int weight;

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

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