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

📓 알고리즘

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

케로⸝⸝◜࿀◝ ⸝⸝ 2024. 4. 18. 11:55

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

다익스트라 알고리즘은 최단 경로 문제 중, 단일 출발(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)$