• 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
• 조건:
  • 가중치가 0 이상인 그래프
  • 음수 간선이 있는 경우 사용할 수 없음 (그럴 땐 벨만-포드 사용)
• 이미지 출처: 나노 바나나 프로 (Nano Banana Pro)

알고리즘

1. 출발 노드의 거리를 0으로 초기화, 나머지는 무한대(INF)로 설정
2. 방문하지 않은 노드 중 가장 가까운 노드 선택
3. 선택한 노드를 경유하여 다른 노드로 가는 거리 갱신
4. 모든 노드 방문 시 종료

   핵심: 탐욕(Greedy) + 최단 거리 갱신

코드 예시

import java.util.*;

class Node implements Comparable<Node> {
    int vertex;
    int weight;

    Node(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }

    public int compareTo(Node other) {
        return this.weight - other.weight;
    }
}

public class DijkstraExample {
    static final int INF = Integer.MAX_VALUE;

    public static int[] dijkstra(List<List<Node>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;
            int w = current.weight;

            if (w > dist[u]) continue; // 이미 더 짧은 경로가 있음

            for (Node neighbor : graph.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int n = 5; // 노드 수
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // 간선 추가: graph.get(u).add(new Node(v, weight));
        graph.get(0).add(new Node(1, 10));
        graph.get(0).add(new Node(3, 30));
        graph.get(0).add(new Node(4, 100));
        graph.get(1).add(new Node(2, 50));
        graph.get(2).add(new Node(4, 10));
        graph.get(3).add(new Node(2, 20));
        graph.get(3).add(new Node(4, 60));

        int start = 0;
        int[] dist = dijkstra(graph, start);

        System.out.println("최단 거리 from node " + start);
        for (int i = 0; i < n; i++) {
            System.out.println("to " + i + ": " + dist[i]);
        }
    }
}