[그래프/개념] 다익스트라 알고리즘(Dijkstra's Algorithm) , 최단경로구하기

다익스트라 알고리즘은 최단 경로 알고리즘 중의 하나입니다.

그래프의 어느 정점 하나를 시작으로 하고,

나머지 정점들로의 최단 거리를 모두 구합니다.

다익스트라 알고리즘이 작동하는 방식은 다음과 같습니다.

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.

2. 해당 정점에서 인접하고, 아직 방문하지 않은 정점들의 거리를 갱신한다.

거리 dist[] 배열을 하나 생성하여 초기값을 셋팅해 줄건데

1번 정점이 시작점이라고 했을때, 자기 자신까지의 거리는 0이기 때문에

시작점으로의 거리만 0으로 셋팅해주고, 나머지는 무한으로 초기값을 셋팅해줍니다.

이렇게 반복해서 동작하고, 끝나고 나면 각 dist 배열에 있는 값이, 

각 정점으로까지의 실제 최단경로가 됩니다.

문제가 될 부분은 아직 방문하지 않은 정점들 중에서

dist값이 제일 작은 정점을 찾아 방문해야 하는데,

이걸 매번 찾으면서 가다가는 시간복잡도가 발생하여 메모리가 초과할 수 있습니다.

따라서, 우선순위큐를 사용하는데,

최소힙을 하나 생성하고, 정점 u를 방문해서, 인접한 정점 v의 거리를 갱신할 때마다,

최소힙에 (dist[v], v) 쌍을 넣습니다.

이렇게 하여 최소힙에서 먼저 나온 아이가 제일 작은 값이 될 거고, 이 값을 사용하면 됩니다.

그럼 다익스트라 알고리즘을 구현해볼게요.

// https://www.acmicpc.net/problem/1753 : 백준 / 최단경로
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static int V, E, K;
    static int u, v, w;
    static ArrayList<Element> list[];
    static long dist[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
 
        list = new ArrayList[V+1];
        for(int i=1; i<=V; i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1; i<=E; i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            list[u].add(new Element(v, w));
        }
        dist = new long[V+1];
        for(int i=1; i<=V; i++){
            dist[i] = Long.MAX_VALUE;
        }
        PriorityQueue<long[]> pq = new PriorityQueue<>(10, new Comparator<long[]>() { // 거리값, 정점번호에 대해 정렬
            @Override
            public int compare(long[] o1, long[] o2) {
                if(o1[0] - o2[0] > 0)   return 1;
                return -1;
            }
        });
 
        dist[K] = 0;
        pq.add(new long[]{0, K}); //거리값, 정점 번호 셋팅
        while(!pq.isEmpty()){
            long d = pq.peek()[0]; //거리
            long curr = pq.peek()[1]; //정점
            pq.poll();
            if(dist[(int) curr] != d)    continue;
 
            for(Element e : list[(int)curr]){
                int next = e.end;
                int wi = e.weight;
                if(dist[next] > dist[(int)curr] + wi){
                    dist[next] = dist[(int)curr] + wi;
                    pq.add(new long[]{dist[next], next});
                }
            }
        }
        for(int i=1; i<=V; i++){
            if(dist[i] == Long.MAX_VALUE)   System.out.println("INF");
            else    System.out.println(dist[i]);
        }
    }
}
class Element {
    int end, weight;
    Element(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
}