다익스트라 알고리즘과 우선순위 큐

📝 다익스트라 알고리즘이란?

• 다익스트라 알고리즘은 최단 경로 문제 중, 단일 출발(single-source shortest path problem) 최단 경로 문제에 해당
• 하나의 정점에서 다른 모든 정점 간의 각각의 가장 짧은 경로를 찾는 문제
• 음의 가중치를 갖지 않는 그래프에서 사용됨

 

📌  예시 문제

아래의 가중치 방향 그래프에서 1번 정점에서 모든 정점으로의 최소 거리 비용을 출력하는 프로그램을 작성하세요.

(단, 경로가 없으면 impossible을 출력한다.)

입력 설명

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.

그다음부터 M줄에 걸쳐 연결 정보와 거리 비용이 주어진다.

 

출력 설명

1번 정점에서 각 정점으로 가는 최소 비용을 2번 정점부터 차례대로 출력하세요.

 

입력 예제

6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

 

출력 예제

2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

 

📝 다익스트라 알고리즘 로직

1. 출발 정점 설정

• 출발 정점을 기준으로 배열을 선언하여, 출발 정점에서 각 정점까지의 거리를 저장한다.
  • 초기에는 출발 정점의 거리는 0, 다른 정점들의 최단 경로는 무한대로 초기화한다.
• 우선순위 큐에 (출발 정점, 거리 0)만 먼저 넣는다.

2. 우선순위 큐에서 정점을 꺼냄

• 처음에는 출발 정점만 저장되어 있으므로, 출발 정점이 꺼내진다.
• 출발 정점에 인접한 정점 각각에 대해, 출발 정점에서 각 정점으로 가는 거리가 현재 배열에 저장되어 있는 거리보다 짧을 경우 최단 거리를 업데이트한다.
• 업데이트된 거리를 우선순위 큐에 넣는다.

3. 2번의 과정을 우선순위 큐에 꺼낼 정점이 없을 때까지 반복한다.

• 단, 우선순위 큐에서 꺼내서 확인할 때, 배열에 기록된 현재까지 발견된 최단 거리보다 더 긴 거리를 가진 (정점, 거리)가 나왔다면 해당 정점과 인접한 정점 간의 거리 계산은 의미가 없으므로 건너뛴다. (아래 구현 코드에서 다시 확인해 보자!)

 

📝 예시로 이해하는 다익스트라 알고리즘

1단계: 초기화

• 출발 정점을 기준으로 배열을 선언하여, 출발 정점에서 각 정점까지의 거리를 저장한다.
  • 초기에는 출발 정점의 거리는 0, 다른 정점들의 최단 경로는 무한대로 초기화한다.
• 이 예시에서 출발 정점은 1번이므로, 1번 정점의 거리는 0이고 나머지는 무한대로 초기화한다.
• 우선순위 큐에 (1번, 0)을 먼저 넣는다.

2단계: 우선순위 큐에서 추출한 (1번, 0) [정점, 출발 정점과의 거리]를 기반으로 인접한 정점과의 거리 계산

• 처음에는 (1번, 0)만 저장되어 있으므로, (1번, 0)이 꺼내진다.
• (1번, 0)에 인접한 정점 (2번, 12), (3번, 4)에 대해, 출발 정점에서 각 정점으로 가는 거리가 현재 배열에 저장되어 있는 거리보다 짧을 경우 최단 거리를 업데이트한다.
• 업데이트된 거리를 우선순위 큐에 넣는다.

 

3단계: 우선순위 큐에서 (3번, 4) [정점, 출발 정점과의 거리]를 기반으로 인접한 정점과의 거리 계산

• 우선순위 큐가 최소 힙(MinHeap) 방식이므로, 우선순위 큐에 넣어진 (3번, 4)과 (2번, 12) 중 (3번, 4)가 먼저 추출된다.
• 해당 정점에 인접한 정점 (4번, 5)에 대해, 출발 정점에서 (4번, 5)으로 가는 거리(출발 정점에서 3번 정점까지 오는 거리 4 + 3번 정점에서 4번 정점까지 오는 거리 5 = 9)가 현재 배열에 저장되어 있는 거리(inf) 보다 짧으므로 최단 거리를 업데이트한다.
• 업데이트된 거리 (4번, 9)를 우선순위 큐에 넣는다. 

 

4단계: 우선순위 큐에서 (4번, 9) [정점, 출발 정점과의 거리]를 기반으로 인접한 정점과의 거리 계산

• 3단계와 동일한 흐름으로 처리된다.

 

5단계: 우선순위 큐에서 (2번, 11) [정점, 출발 정점과의 거리]를 기반으로 인접한 정점과의 거리 계산

• 3단계와 동일한 흐름으로 처리된다.
• 단, 계산 시 현재 배열에 저장되어 있는 거리가 더 짧기 때문에 업데이트 되지 않고 우선순위 큐에도 넣지 않는다.

 

6단계: 우선순위 큐에서 (2번, 12) 꺼내고 건너뜀

• 위에서 언급했던 것처럼 우선순위 큐에서 꺼내서 확인할 때, 배열에 기록된 현재까지 발견된 최단 거리보다 더 긴 거리를 가진 (정점, 거리)가 나왔다면 해당 정점과 인접한 정점 간의 거리 계산은 의미가 없으므로 건너뛴다.
• if (nowCost > dis[nowNodeNum]) continue;

 

7단계: 우선순위 큐에서 (5번, 14) 꺼내고, 인접한 정점이 없으므로 우선순위 큐에 넣을 것이 없음

 

8단계: 큐가 비었으므로 종료

 

📌 예시 문제 구현

import java.util.*;

class Edge implements Comparable<Edge> {
    private int nodeNum;
    private int cost;

    public Edge(int nodeNum, int cost) {
        this.nodeNum = nodeNum;
        this.cost = cost;
    }

    public int getNodeNum() {
        return nodeNum;
    }

    public void setNodeNum(int nodeNum) {
        this.nodeNum = nodeNum;
    }

    public int getCost() {
        return cost;
    }

    public void setCost(int cost) {
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }
}

public class Main
{
    static int numOfNodes, numOfEdges;
    static ArrayList<ArrayList<Edge>> graph;
    static int[] dis;
    
    public static void main(String[] args) {
        Main q = new Main();
        
        Scanner scanner = new Scanner(System.in);
        numOfNodes = scanner.nextInt();
        numOfEdges = scanner.nextInt();

        // 연결 정보 저장용
        graph = new ArrayList<>();
        for (int i = 0; i <= numOfNodes; i++) {
            graph.add(new ArrayList<>());
        }

        // 최소 거리 저장용
        dis = new int[numOfNodes + 1];
        Arrays.fill(dis, Integer.MAX_VALUE);

        // 연결 정보 저장
        for (int i = 0; i < numOfEdges; i++) {
            int node1 = scanner.nextInt();
            int node2 = scanner.nextInt();
            int cost = scanner.nextInt();
            graph.get(node1).add(new Edge(node2, cost));
        }

        q.solution(1);

        for (int i = 2; i <= numOfNodes; i++) {
            if (dis[i] != Integer.MAX_VALUE) {
                System.out.println(i + " : " + dis[i]);
            } else {
                System.out.println("impossible");
            }
        }
    }
    
    private void solution(int nodeNum) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(nodeNum, 0));
        dis[nodeNum] = 0;
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int nowNodeNum = now.getNodeNum();
            int nowCost = now.getCost();
            if (nowCost > dis[nowNodeNum]) {
                continue;
            }
            for (Edge next : graph.get(nowNodeNum)) {
                int nextNodeNum = next.getNodeNum();
                int tempCost = nowCost + next.getCost();
                if (tempCost < dis[nextNodeNum]) {
                    dis[nextNodeNum] = tempCost;
                    pq.offer(new Edge(nextNodeNum, tempCost));
                }
            }
        }
    }
}

 

📝 우선순위 큐 사용 장점

• 지금까지 발견된 가장 짧은 거리의 정점에 대해서 먼저 계산
• 더 긴 거리로 계산된 경로에 대해서는 계산을 스킵할 수 있음

 

📝 시간 복잡도

간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 $O(ElogV)$가 된다.

우선순위 큐에서 꺼낸 노드는 연결된 노드만 탐색하므로 최악의 경우라도 총 간선 수인 E만큼만 반복한다. 즉 하나의 간선에 대해서는 $O(logE)$이고, E는 $V^{2}$보다 항상 작기 때문에 E개의 간선을 우선순위 큐에 넣었다 빼는 최악의 경우에 대해서는 $O(ElogV)$이다.

 

💡 참고 (힙의 시간 복잡도)

• depth(트리의 높이)를 h라고 표기한다면, n개의 노드를 가지는 heap에 데이터 삽입 또는 삭제 시 최악의 경우 root 노드에서 leaf 노드까지 비교해야 한다.
• $h = log2n$에 가까우므로, 시간복잡도는 $O(logn)$