[ 알고리즘 ] Dijkstra Algorithm

• 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘

⚠️ 음의 가중치를 가지지 않는 그래프에서만 동작(음의 가중치 → Bellman-Ford Algorithm)

🔎 핵심

1. 그래프 : edge에는 weight(가중치) 존재
2. 최단 경로
3. 탐욕 알고리즘 기반 : 현재 가장 비용이 적은 경로를 우선적 탐색

🔎 Flow

1. 초기화
   • 시작 노드의 최단 거리 = 0
   • 나머지 모든 노드의 거리 = ∞
   • 방문하지 않은 노드 배열(or 우선순위 큐 생성)
2. 방문 처리
   • 최단 거리 업데이트 필요 없는 노드는 방문 완료로 처리
   • 방문하지 않은 노드 중 최단 거리가 가장 작은 노드를 선택해 탐색
3. 최단 거리 업데이트
   • 현재 노드에서 연결된 인접 노드들의 최단 거리 계산 → 기존의 최단 거리보다 작다면 갱신
4. 모든 노드를 방문할 때까지 반복

---

🔎 배열

import java.util.*;

public class DijkstraExample {

        // graph[i][j] : i번 노드에서 j번 노드로의 가중치, 0이면 연결X
    public static void dijkstra(int[][] graph, int start) {

        int n = graph.length; // 노드 개수
        int[] dist = new int[n]; // 시작 노드에서 각 노드까지 최단 거리 저장 배열
        boolean[] visited = new boolean[n]; // 방문 여부 확인 배열(최단 거리가 확정되었는지)

        **// 1. 거리 배열 초기화 (무한대 값으로)**
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0; // 시작 노드 거리 0

        // 다익스트라 알고리즘
        for (int i = 0; i < n; i++) {

            **// 2. 방문하지 않은 노드 중 최단 거리 노드 선택**
            int minNode = -1;
            int minDist = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                    // 방문하지 않았고, 저장된 최단 거리보다 거리가 작다면 
                if (!visited[j] && dist[j] < minDist) {
                        // 노드, 최단 거리 업데이트
                    minNode = j;
                    minDist = dist[j];
                }
            }

            **// 최단 거리 노드 방문**
            visited[minNode] = true;

            **// 3. 선택된 노드의 인접 노드들의 거리 갱신**
            for (int j = 0; j < n; j++) {

                    // 인접 노드로 연결된 edge가 존재하고, 방문하지 않은 경우
                if (graph[minNode][j] != 0 && !visited[j]) {

                        // 시작노드~ j노드 까지 거리
                        // = 시작노드에서 현재 edge까지 거리 + 현재 edge 에서 인접노드(j) 거리
                    int newDist = dist[minNode] + graph[minNode][j];

                    // 기존의 최단 거리보다 작다면
                    if (newDist < dist[j]) {
                        dist[j] = newDist; // 거리 갱신
                    }
                }
            } 
            **// 4. 모든 노드를 방문할 때까지 반복** 
        }

        // 결과 출력
        System.out.println("노드 " + start + "에서의 최단 거리:");
        for (int i = 0; i < n; i++) {
            System.out.println("노드 " + i + " : " + dist[i]);
        }
    }

    public static void main(String[] args) {
        // 예제 그래프 (인접 행렬로 표현)
        int[][] graph = {
            {0, 1, 4, 0, 0},
            {1, 0, 2, 6, 0},
            {4, 2, 0, 3, 1},
            {0, 6, 3, 0, 2},
            {0, 0, 1, 2, 0}
        };
        int startNode = 0; // 시작 노드 (0번 노드)

        dijkstra(graph, startNode);
    }
}

---

🔎 우선순위 큐 (Prioirty Queue)

• 일반적으로 최소 힙(Min-Heap)으로 구현

import java.util.*;

public class DijkstraExample{

    public static void dijkstra(List<List<int[]>> graph, int start) {

        int n = graph.size(); // 노드 개수
        int[] dist = new int[n]; // 최단 거리 저장 배열

        **// 1. 초기화**
        Arrays.fill(dist, Integer.MAX_VALUE); // 초기값을 무한대로 설정
        dist[start] = 0; // 시작 노드의 거리는 0

        // 우선순위 큐에 [노드, 거리]를 저장
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[] { start, 0 }); // 시작 노드를 큐에 삽입

        while (!pq.isEmpty()) {

            **// 2. 방문하지 않은 노드 중 최단 거리 노드 선택**
            int[] current = pq.poll(); // 가장 비용이 작은 노드 선택
            int now = current[0];
            int nowCost = current[1];

            // 이미 처리된 노드라면 무시
            if (nowCost > dist[now]) continue;

            // 현재 노드의 인접 노드 확인
            for (int[] neighbor : graph.get(now)) {
                int next = neighbor[0];
                int nextCost = nowCost + neighbor[1];

                                //3. **최단 거리 업데이트**
                // 더 짧은 경로를 발견하면 갱신
                if (nextCost < dist[next]) {
                    dist[next] = nextCost;
                    pq.offer(new int[] { next, nextCost }); // 갱신된 정보를 큐에 삽입
                }
            }
            **// 4. 모든 노드를 방문할 때까지 반복** 
        }

        // 결과 출력
        System.out.println("노드 " + start + "에서의 최단 거리:");
        for (int i = 0; i < n; i++) {
            System.out.println("노드 " + i + " : " + dist[i]);
        }
    }

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

        // 그래프 초기화
        graph.get(0).add(new int[] { 1, 1 });
        graph.get(0).add(new int[] { 2, 4 });
        graph.get(1).add(new int[] { 0, 1 });
        graph.get(1).add(new int[] { 2, 2 });
        graph.get(1).add(new int[] { 3, 6 });
        graph.get(2).add(new int[] { 0, 4 });
        graph.get(2).add(new int[] { 1, 2 });
        graph.get(2).add(new int[] { 3, 3 });
        graph.get(2).add(new int[] { 4, 1 });
        graph.get(3).add(new int[] { 1, 6 });
        graph.get(3).add(new int[] { 2, 3 });
        graph.get(3).add(new int[] { 4, 2 });
        graph.get(4).add(new int[] { 2, 1 });
        graph.get(4).add(new int[] { 3, 2 });

        int startNode = 0; // 시작 노드
        dijkstra(graph, startNode);
    }
}

• [ 프로그래머스 ] #12978 : 배달 - JAVA