다익스트라(Dijkstra) 알고리즘이란?

다익스트라 알고리즘(Dijkstra’s Algorithm)은 가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

또한 여러 가지 최단 거리를 구하는 알고리즘이 있짐만 다익스트라 알고리즘은 간선의 가중치는 무조건 0이상(음수 불가능!!!!!!)이라는 제약 조건이 따른다.

최단 거리를 구하는 알고리즘 종류

알고리즘	음수 간선	출발점	시간복잡도	주요 용도
BFS	❌	단일	O(V+E)	가중치 = 1
다익스트라	❌	단일	O((V+E)logV)	실전 최다 사용
벨만-포드	✅	단일	O(VE)	음수 간선
플로이드-워셜	✅	전체	O(V³)	모든 쌍
SPFA	✅	단일	평균 빠름	실무/주의
0-1 BFS	0/1	단일	O(V+E)	가중치 0,1

다익스트라 알고리즘의 특징

다익스트라 알고리즘의 핵심은 크게 3가지가 있다.
1. 간선의 가중치는 무조건 0 이상 -> 음수 불가능
2. 방향/무방향 그래프 모두 적용 가능
3. 그리디 알고리즘 + 최단 거리 확정 방식

주로 A 시작점에서 B 도착점까지의 최소 비용(최소 거리)를 물어보며, 한 노드에서 모든 노드까지의 최단 거리를 물어보기도 한다.

또한 이 알고리즘의 핵심은 바로 그리디(Greedy) 방식을 사용한다는 것이다.
즉, 현재까지 가장 가까운 정점부터 확정하며 점차 늘려가는 것이며, 그 과정에서 우선순위 큐를 사용한다.

알고리즘의 동작 원리

1. 시작 정점의 거리를 0으로 설정
2. 나머지 정점의 거리는 INF(무한대)로 초기화
3. 확정되지 않은 정점 중 거리 값이 가장 작은 정점을 선택
4. 해당 정점을 기준으로 인접 정점들의 거리 갱신
5. 더 이상 갱신할 정점이 없을 때까지 반복

이 중에서 가장 핵심 연산은 Relaxtion(완화)이다.
현재 정점을 거쳐 가는 경로가 기존에 알던 경로보다 짧으면 갱신하는 것이다.

if (dist[next] > dist[cur] + weight) {
    dist[next] = dist[cur] + weight;
}

다익스트라의 시간복잡도

단순 배열 기반으로 문제를 풀면 시간 복잡도가 O(V²)으로 시간초가 매우 넉넉하거나 주어진 N의 수가 매우 적은 경우 가능하지만 조금만 N의 수가 높아지면 시간 초과가 발생한다.
따라서 가중치가 만약 모두 양수 또는 0이라면 바로 다익스트라 알고리즘을 떠올리는 것이 좋다.
다익스트라의 시간 복잡도는 O((V + E) log V)으로 확 줄어들게 된다.

cf) V = 정점 수, E = 간선 수

cf) 가중치가 음수가 존재한다면 벨맨-포드 알고리즘을 적용하는 것이 좋다.

다익스트라 알고리즘의 적용 예시

https://www.acmicpc.net/problem/1916

import java.io.*;
import java.util.*;

public class boj_1916_G5 {

    static class Edge {
        int to;
        int cost;
        
        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    static class Node implements Comparable<Node> {
        int v;
        long dist;
        
        Node(int v, long dist) {
            this.v = v;
            this.dist = dist;
        }
        
        @Override
        public int compareTo(Node o) {
            return Long.compare(this.dist, o.dist);
        }
    }

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        List<Edge>[] graph = new ArrayList[N + 1];
        
        for (int i = 1; i <= N; i++) {
        	graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            
            graph[from].add(new Edge(to, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        long[] dist = new long[N + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (cur.dist != dist[cur.v]) continue;
            if (cur.v == end) break;

            for (Edge e : graph[cur.v]) {
                long nd = cur.dist + e.cost;
                
                if (nd < dist[e.to]) {
                    dist[e.to] = nd;
                    pq.offer(new Node(e.to, nd));
                }
            }
        }

        System.out.println(dist[end]);
    }
}

cf) dist에는 int보다는 long을 사용하는 것이 더 좋다.
-> 각 간선이 int의 수여도 누적 거리가 되어버리면 int의 최대값을 초과하는 경우가 생기기에 long을 사용하는 것을 추천한다.