[알고리즘] 다익스트라 알고리즘 (Dijkstra)

다익스트라 알고리즘

그래프에서 하나의 시작점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다.
매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

동작 흐름

1. 출발 노드와 도착 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 현재 위치한 노드의 인접 노드 중, 방문하지 않은 노드를 구별하고
   방문하지 않은 노드 중, 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 최단 거리 테이블을 업데이트한다.
5. 3 ~ 4번의 과정을 반복한다.

[그래프 예시 사진 추가 예정]

다익스트라 알고리즘 특징

다익스트라 알고리즘은 방문하지 않은 노드 중, 최단 거리인 노드를 선택하는 과정을 반복한다.

또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.

도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요가 없다.

가중치가 양수일 때만 사용 가능하다.

다익스트라 알고리즘  구현 방법

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

public class Main {

    static class Node implements Comparable<Node> {
        int to;
        int cost;

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

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost; // 비용 기준 오름차순
        }
    }

    static int N, M;
    static List<Node>[] graph;
    static int[] dist;
    static final int INF = 1_000_000_000;

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

        N = Integer.parseInt(br.readLine());  // 노드 개수
        M = Integer.parseInt(br.readLine());  // 간선 개수

        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 u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph[u].add(new Node(v, w));
        }

        int start = Integer.parseInt(br.readLine());

        dijkstra(start);

        for (int i = 1; i <= N; i++) {
            if (dist[i] == INF) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }

    static void dijkstra(int start) {
        dist = new int[N + 1];
        Arrays.fill(dist, INF);

        PriorityQueue<Node> pq = new PriorityQueue<>();

        dist[start] = 0;
        pq.add(new Node(start, 0));

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

            // 이미 더 짧은 경로가 있으면 skip
            if (cur.cost > dist[cur.to]) continue;

            for (Node next : graph[cur.to]) {
                if (dist[next.to] > dist[cur.to] + next.cost) {
                    dist[next.to] = dist[cur.to] + next.cost;
                    pq.add(new Node(next.to, dist[next.to]));
                }
            }
        }
    }
}

다익스트라 알고리즘 대표 문제

백준 1753번 : 최단경로

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

-> 우리가 알고 있는 다익스트라 알고리즘 그대로 적용하면 풀 수 있음

백준 11779번 : 최소비용 구하기 2

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

-> 시작 노드에서 끝 노드까지의 경로를 표현하기 위해서 parent 배열 활용이 필요함

다익스트라 알고리즘으로 최단 거리 테이블 초기화 하는 과정에서 parent 배열도 초기화 해주자

paent[next] = cur.to