[ Java ] 다익스트라(Dijkstra) 알고리즘 개념 및 최적화

개념

다익스트라(Dijstra) 알고리즘은 대표적인 최단 경로 ( Shortest Path ) 탐색 알고리즘입니다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다. 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.

이때 음의 간선은 존재하지 않으며, 정점에 있는 모든 간선은 양수로 구성되어 있습니다.
다익스트라 알고리즘이 다이나믹 프로그래밍인 이유는 해당 최단 거리는 다른 최단 거리로 이루어져있기 때문입니다. 다익스트라는 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리를 사용해야하는 특징을 가지고 있습니다.

예시

다익스트라는 기본적으로 시작 정점에서 시작하여 간선의 가중치를 이용하여 초기 가중치 표를 구성합니다. 이때 갱신된 정점 중에서 가중치가 가장 낮은 정점 순서대로 진입하여 나머지 정점에 대한 가중치를 비교하고 갱신하는 과정을 반복합니다.

다음과 같은 그래프가 있습니다. 만약 1 을 기준으로 모든 정점의 최단 거리를 계산 하려고 합니다.
정점 1번에서 간선을 통해 갈 수 있는 정점은 2 , 3 , 4 가 있으며 해당 정점으로 갈 수 있는 비용은 다음과 같습니다.

정점	1	2	3	4
가중치	0	3	6	7

그 다음 가중치가 가장 낮은 정점 3을 기준으로 각 정점에 대한 가중치를 다시 비교합니다.

정점	1	2	3	4
가중치	0	3	4	7

이때 정점 2는 1과 3만 연결되어 있습니다. 이때 정점 3은 본인의 가중치 ( 3 ) + 3으로 가는 가중치 ( 1 ) 이 4이므로 기존 가중치인 6보다 낮기 때문에 갱신됩니다.

정점	1	2	3	4
가중치	0	3	4	7

그 다음 가중치가 가장 짧은 정점 3 에 접근을 하여 연결된 1 , 2 , 4 와 모두 탐색을 합니다.

이때 정점 3에서 4로 가는 가중치는 기존 7 보다 빠른 5이므로 갱신됩니다. ( 정점 4 + 가중치 1 )

마지막 정점 4는 더이상 갱신되지 않음으로 갱신 되는 정점 없이 바로 종료됩니다. 따라서 최종 결과값은 다음과 같습니다.

정점	1	2	3	4
가중치	0	3	4	7

주의 사항

이때 다익스트라의 시간 복잡도는 O ( N ^ 2 ) 를 띄우게 됩니다. 가장 적은 가중치를 찾는 시간 N과 찾은 정점을 기준으로 갱신되는 가중치가 있는지 확인하는 여부 N 으로 인해 N ^ 2 가 됩니다.

이때 힙 구조 ( 우선 순위 큐 ) 를 사용한다면 O ( N Log N ) 이 될 수 있습니다. 가장 적은 가중치를 찾는 데 힙 구조를 사용하면 N 이 아닌 Log N 으로 해결할 수 있죠 ( 힙에 데이터를 넣고 정렬하는 시간 )

구현

O ( N log N ) 시간 복잡도를 갖는 코드

class Node {
    int index;
    int time;

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

    @Override
    public String toString() {
        return "[Node -> " + index + " / time -> " + time + " ]";
    }
}

class Main {

    static boolean visited[];
    static int N , M , K , X;
    final static int INF = 100_000_000;
    static int time[];
    static ArrayList<Integer>[] maps;
    static PriorityQueue<Node> queue = new PriorityQueue<>((n1 , n2) -> n1.time - n2.time);


    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        maps = new ArrayList[N + 1];
        for(int i = 0; i <= N; i++) {
            maps[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine() , " ");

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            maps[start].add(end);
        }

        // 다익스트라
        visited = new boolean[N + 1];
        time = new int[N + 1];
        Arrays.fill(time , INF);
        time[X] = 0;
        queue.add(new Node(X , 0));

        while(!queue.isEmpty()) {
            Node node = queue.poll();

            Dijkstra(node);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; i++) {
            if(time[i] == K) {
                sb.append(i).append("\n");
            }
        }

        if(sb.length() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(sb);
        }
    }

    public static void Dijkstra(Node node) {
        visited[node.index] = true;
        int nextTime = time[node.index] + 1;

        if(nextTime > K) return;

        for(int next : maps[node.index]) {
            if(time[next] > nextTime) {
                time[next] = nextTime;
                queue.offer(new Node(next , nextTime));
            }
        }
    }
}

O ( N ^ 2 ) 시간 복잡도를 갖는 코드

class Main {

    static boolean visited[];
    static int N , M , K , X;
    final static int INF = 100_000_000;
    static int time[];
    static ArrayList<Integer>[] maps;


    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        maps = new ArrayList[N + 1];
        for(int i = 0; i <= N; i++) {
            maps[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine() , " ");

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            maps[start].add(end);
        }

        // 다익스트라
        visited = new boolean[N + 1];
        time = new int[N + 1];
        Arrays.fill(time , INF);
        time[X] = 0;

        for(int i = 1; i <= N; i++) {
            int result = findMin();

            Dijkstra(result);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; i++) {
            if(time[i] == K) {
                sb.append(i).append("\n");
            }
        }

        if(sb.length() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(sb);
        }
    }

    public static int findMin() {
        int min = INF;
        int result = INF;

        for(int i = 1 ; i <= N; i++) {
            if(!visited[i] && time[i] < min) {
                min = time[i];
                result = i;
            }
        }

        return result;
    }

    public static void Dijkstra(int index) {
        visited[index] = true;

        for(int next : maps[index]) {
            int nextTime = time[index] + 1;

            if(time[next] > nextTime) {
                time[next] = nextTime;
            }
        }
    }
}