Dijkstra (다익스트라)

다익스트라 알고리즘은 그래프 간선정보(단/양방향 상관X)가 주어졌을 때 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 그러나 음수 가중치 간선이 존재하는 경우 사용할 수 없다. 해당 경우에는 벨만 포드 알고리즘을 사용해야 한다.

다익스트라 알고리즘의 핵심은 현재 갈 수 있는 거리 중 매번 가장 짧은 정점을 찾으면, 논리적으로 더 짧은 경로가 새로 발견될 수 없기 때문에 해당 정점까지의 가장 짧은 거리는 그 순간에 확정되는 것이다.

그러면 인접 노드 중 가장 짧은 노드를 찾기 위해 우선순위 큐를 사용하면 된다. 만약에 특정 순간에 가장 거리가 짧은 정점을 확정을 지었어도, 다른 노드 B로부터 시작 정점->노드 B -> 해당 정점까지의 거리를 기록한 노드(해당 정점까지의 누적 거리합)이 우선순위 큐에 여전히 남아있을 수도 있다.

그러나 이 부분은 인접 노드 삽입 시 매번 해당 노드로의 가장 작은 거리를 찾아 업데이트 했던 dist 배열에서 일치여부를 확인 if (d > dist[u]) continue; 하여 일치하지 않는다면(최단 거리로 갱신된 정보가 아니라면) 건너뛴다.
*d 는 우선순위큐에서 뽑은 정점까지의 누적 거리
*w 는 뽑은 정점이 가지고 있었던 특정 인접 정점까지의 거리 정보

for문 내부에서 if (dist[v] > d + w) 이 조건문은 최단거리를 갱신된 정점에 대해 인접한 정점들을 돌면서, 기존에 기록했던 인접 정점까지의 최단거리(dist[v])보다, 최단거리 갱신 정점을 거쳐서 해당 노드로 가는게 더 빠른 경우에만 dist 를 갱신하고, 우선순위 큐에 삽입해주면 된다.

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

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

class PQNode implements Comparable<PQNode> {
    int vertex;
    int dist; // 시작점으로부터의 현재까지의 거리
    PQNode(int vertex, int dist) {
        this.vertex = vertex;
        this.dist = dist;
    }
    @Override
    public int compareTo(PQNode o) {
        return Integer.compare(this.dist, o.dist); // 최소 힙
    }
}

public class Main {

    static final int INF = 1_000_000_000;
    static int V, E, K;
    static int[] dist;
    static List<Edge>[] graph;

    public static void main(String[] args) throws IOException {
        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());  // 시작 정점

        dist = new int[V + 1];
        Arrays.fill(dist, INF);

        graph = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < E; i++) {
            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 Edge(v, w));
        }

        dijkstra(K);

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

    static void dijkstra(int start) {
        PriorityQueue<PQNode> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.offer(new PQNode(start, 0));

        while (!pq.isEmpty()) {
            PQNode cur = pq.poll();
            int u = cur.vertex;
            int d = cur.dist;

            // 최신 거리만 처리
            if (d != dist[u]) continue;

            for (Edge edge : graph[u]) {
                int v = edge.to;
                int w = edge.weight;

                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.offer(new PQNode(v, dist[v]));
                }
            }
        }
    }
}