[Algorithm] 우선순위 큐를 활용한 다익스트라 알고리즘

다익스트라 알고리즘 (Using Priority Queue)

다익스트라 알고리즘의 기본 구성은 지난 포스트에서 다뤘다. 다익스트라는 한 노드에서 다른 노드들까지 가는 모든 최소 비용을 구하는 알고리즘이었다. 여기서 두 가지 과정을 반복적으로 수행하면서 목적을 달성하게 된다.

• 방문하지 않은 노드들 중에 가장 비용이 적은 노드를 다음 노드로 삼는다. (그리디 알고리즘)
• 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍)

여기서 방문하지 않은 노드들 중에 가장 비용이 적은 노드를 찾기 위해 최악의 경우 모든 노드를 살펴봐야 할 수도 있다는 점이 최적화할 수 있는 부분이었다. 이를 개선하기 위한 방법 중 우선순위 큐를 활용한 다익스트라를 구현해보려고 한다.

---

다익스트라 알고리즘 구현 (Using Priority Queue)

기본적으로 다익스트라 알고리즘은 최소 비용을 갖는 노드를 선택하고, 주변 노드의 값을 갱신한다. 여기서 생각해볼 것은 비용 배열에서 갱신된 노드를 제외하고는 여전히 최대값(혹은 무한대 값)을 갖고 있기 때문에 이 과정에서 고려할 필요가 없다. 즉, 갱신하는 주변 노드의 값에 대해서만 다음 최소 비용을 갖는 노드를 선택해주면 된다는 것이 우선순위 큐를 사용하는 것의 핵심이다.

 

우선순위 큐에 삽입되는 노드의 수가 바로 갱신해야 하는 주변 노드의 수라는 말이다. 다르게 하면 갱신해야하는 주변 노드의 수 = 갱신해야 하는 주변 노드로의 간선의 수라는 말도 된다. 정리하자면 즉, 우선순위큐에 삽입되는 노드의 수는 해당 노드(V)와 연결된 간선(E)의 개수이다. 또한 추출을 할때는 최대 V개의 노드에 대해서 우선순위큐에서 추출할 것이다. 그래서 시간복잡도는 최악의 경우 O((V+E)logV이고 최선의 경우는 O(ElogV)가 된다.

 

시간복잡도의 핵심은 추출 연산, 삽입 연산(poll() : 최소 비용을 뽑는 연산, offer() : 최소 비용 후보를 큐에 넣는 연산)이다. 

 

package Z_Algorithm.Dijkstra;

import Z_DataStructure.PriorityQueue.PriorityQueue;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */
public class DijkstraUsingPriorityQueue {

    static int V, E, start;
    static ArrayList<ArrayList<Node>> graph;

    static class Node {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());
        graph = new ArrayList<ArrayList<Node>>();

        for (int i = 0; i < V + 1; i++) {
            graph.add(new ArrayList<Node>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            // s -> e 의 단방향이다.
            graph.get(s).add(new Node(e, c));
        }

        // 거리 배열 초기화
        int[] dist = new int[V + 1];
        for (int i = 0; i <= V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        // 다익스트라 알고리즘의 최소 비용을 기준으로 추출해야 한다.
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));

        // start -> start 로 가는 것이 초기에는 최소 비용이다.
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            // pq 에서 꺼내진 노드는 현재 최소 비용을 갖는 노드이다.
            Node curNode = pq.poll();

            /**
             *  현재 노드의 비용이 기록된 비용보다 크다면 더 이상 확인할 필요가 없다.
             *  이 조건이 누락된다면 중복 방문이 일어나게 되어 완전그래프의 경우 시간복잡도가 E^2에 수렴할 가능성이 커진다.
             */
            if (dist[curNode.idx] < curNode.cost) {
                continue;
            }

            for (int i = 0; i < graph.get(curNode.idx).size(); i++) {
                Node nextNode = graph.get(curNode.idx).get(i);

                if (dist[nextNode.idx] > curNode.cost + nextNode.cost) {
                    dist[nextNode.idx] = curNode.cost + nextNode.cost;
                    pq.offer(new Node(nextNode.idx, nextNode.cost));
                }
            }

        }

        System.out.println(Arrays.toString(dist));
    }
}

 

---

정리

지난 포스트에 이어 다익스트라 알고리즘에 대해 알아보았다. 구현하면서 시간복잡도에 대해서 주의해야할 것들을 짚어보았고 각 로직들이 구현된 조건들에 대해서도 더 깊게 생각해보게 됐다.

 

다익스트라를 처음 접했을 때는 그래프를 인접행렬, 인접리스트로 구현하느냐에 따라서도 달라지고 우선순위큐 활용여부가 그냥 편해서 하는가보다 했었는데 확실한 이유를 알게 된 이번 포스팅이었다. 꾸준하게 깊게 공부해보는 시간을 가져볼 것이다.