[Algorithm] 다익스트라(Dijkstra)

다익스트라(Dijkstra)?

다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다.

 

특징

그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다.

음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다.

 

구현

P[A][B]는 A와 B사이의 거리라고 가정한다.

1. 출발점으로부터 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정한다.
2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
3. A로 부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.
4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
7. "미방문 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3 ~ 7의 과정을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

 

다음 코드는 [Baekjoon] 1753: 최단경로를 기준으로 작성하였다.

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q1753 {

    private static int v;
    private static int[] weights;
    private static List<List<int[]>> graph;

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

		// 그래프 입력 받는 부분 - start
        String[] ve = br.readLine().split(" ");
        v = Integer.parseInt(ve[0]);
        int e = Integer.parseInt(ve[1]);

        weights = new int[v + 1];
        graph = new ArrayList<>();

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

        for (int i = 0; i <= v; i++) {
            weights[i] = Integer.MAX_VALUE;
        }

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

        for (int i = 0; i < e; i++) {
            String[] uvw = br.readLine().split(" ");
            int u = Integer.parseInt(uvw[0]);
            int v = Integer.parseInt(uvw[1]);
            int w = Integer.parseInt(uvw[2]);
            graph.get(u).add(new int[]{v, w});
        }
        // 그래프 입력받는 부분 - end
        
        search(start);
        printResult();
    }

    public static void search(int start) {
    	// 우선순위 큐를 통해 가중치가 제일 낮은 정점 방문
        Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(c -> c[0]));
        pq.offer(new int[]{0, start});
        weights[start] = 0;

        while (!pq.isEmpty()){
            int[] poll = pq.poll();
            int curWeight = poll[0];
            int curVertex = poll[1];

			// 현재 정점의 가중치가 지나온 길의 가중치합보다 낮다면 건너뜀
            if (weights[curVertex] < curWeight) {
                continue;
            }

            for (int[] next : graph.get(curVertex)) {
                int nextVertex = next[0];
                int nextWeight = next[1];

				// 다음 방문할 정점의 가중치가 현재 지나온 가중치들의 합보다 작다면 갱신하고 방문
                if (weights[nextVertex] > weights[curVertex] + nextWeight) {
                    pq.offer(new int[]{weights[curVertex] + nextWeight, nextVertex});
                    weights[nextVertex] = weights[curVertex] + nextWeight;
                }
            }
        }
    }
    
    private static void printResult() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= v; i++) {
            sb.append(weights[i] == Integer.MAX_VALUE ? "INF" : weights[i]).append("\n");
        }
        System.out.print(sb);
    }

}