다익스트라 알고리즘

---

• 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리 구하는 알고리즘
• 그리디 + 다이나믹 프로그래밍 기법 사용한 알고리즘
• 시간복잡도: O((V+E)log V)
  • 만약 연결 그래프라면 O(E log V)
  • V: 노드 개수, E: 간선 개수

알고리즘 메커니즘

1. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 (그리디)
2. 해당 노드로부터 갈 수 있는 노드들의 비용 갱신 (DP)

🖼️ 그림설명

백준 1753번 : 최단 경로

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

public class 최단경로 { // bj1753

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());

        List<Node>[] list = new ArrayList[v+1];
        for(int i=1; i<=v; i++)
            list[i] = new ArrayList<>();

        for(int i=0; i<e; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[to].add(new Node(from, w)); // 방향이 있었음
        }

        int[] dist = new int[v+1];
        int INF = Integer.MAX_VALUE;
        for (int i = 1; i < v+1; i++)
            dist[i] = INF;


        solution(list, dist, v, k);

        for(int i=1; i<=v; i++)
            System.out.println(dist[i] == INF ? "INF" : dist[i]);

    }

    static class Node {
        int node, cost;
        public Node(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }
    }

    static void solution(List<Node>[] list, int[] dist, int v, int start) {
        // 최소 비용 먼저 꺼내기 위해 가중치 오름차순
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        boolean[] check = new boolean[v+1];

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

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

            if(check[cur.node]) continue;
            check[cur.node] = true; // 방문 체크

            for(Node next : list[cur.node]) {
                // 가려고 하는 노드가 방문하지 않았고(!check[next.node])
                // 가려고하는 노드(next.node)의 지금까지 저장된 거리(dist[next.node])보다
                // 현재 노드를 거쳐 해당 노드(cur.cost + next.cost)로 가는 거리가 더 작으면 갱신
                if(!check[next.node] && dist[next.node] > cur.cost+next.cost) {
                    dist[next.node] = cur.cost+next.cost;
                    q.add(new Node(next.node, dist[next.node]));
                }
            }
        }
    }

}