🤔 다익스트라 알고리즘(Dikstra)이란?

다익스트라 알고리즘은 방향성을 가지는 그래프에서 최단 거리를 구할 때 사용된다. 가중치가 있는 그래프의 최단 경로를 구하는 문제들은 대부분 다익스트라 알고리즘을 사용한다고 보면 된다. 다익스트라 알고리즘은 너비 우선 탐색(BFS)과 유사한 형태를 가진 알고리즘으로, 시작점에서 가까운 순서대로 노드를 방문해간다. 차이점이 있다면 가중치가 있기 때문에 우선 순위 큐(PriorityQueue)를 사용하여 이를 해결하면 된다는 것이다.

 

다익스트라의 핵심은, 현재까지 알려진 최단 거리 중 가장 짧은 노드부터 확정해가면서, 그 노드로부터 뻗어 나가는 간선을 갱신하면 된다는 것이다. 동작 흐름은 대략 아래와 같다.

1. 일단 각 노드까지의 최단 거리를 담을 배열 dist[]에 시작 노드에 대한 최단 거리만 0으로 초기화하고, 나머지는 INF로 초기화한다.

2. 우선 순위 큐에 시작 노드를 삽입한다.

3. 현재 dist가 가장 작은 노드를 꺼낸다.

4. 그 노드로부터 뻗어나가는 간선을 전부 검사한다.

5. 더 짧아지면 갱신하고 우선 순위 큐에 삽입한다.

6. 모든 노드가 확정되면 종료한다.

 

import java.util.*;

class Solution {
	static class Node {
		int destination;
		int cost;
				
		public Node(int destination, int cost) {
			this.destination = destination;
			this.cost = cost;
		}
	}
		
	public int[] dijkstra(int N, int[][] edges, int start) {
       	// 1) 그래프 구성 (인접 리스트)
      	List<Node>[] graph = new ArrayList[N + 1];  // 노드 번호가 양수임을 가정
       	for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
    	}

        // edges: [시작 노드, 목적지 노드, 가중치]
        for (int[] e : edges) {
            int from = e[0];
            int to = e[1];
            int w = e[2];
            graph[from].add(new Node(to, w));
            graph[to].add(new Node(from, w)); // 무방향이면 추가
        }

        // 2) dist 초기화
        int INF = Integer.MAX_VALUE;
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        // 3) cost가 작은 Node부터 먼저 꺼내는 큐
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
        pq.offer(new Node(start, 0));  // 시작점에서 시작

        // 4) 다익스트라 알고리즘
        while (!pq.isEmpty()) {
            Node cur = pq.poll();  // cost가 가장 작은 노드 뽑기
            int now = cur.destination;  // 지금 확정하려는 노드
            int nowCost = cur.cost;  // cur와 now까지의 가중치
            
            if (dist[now] < nowCost) {  // 만약 더 적은 가중치를 알고 있다면, 지금 꺼낸건 버려라
		    	continue;
            }

            for (Node next : graph[now]) {  // now에서 갈 수 있는 모든 이웃을 확인
                int nextNode = next.destination;  // now에서 갈 수 있는 다음 노드
                int edgeCost = next.cost;  // now에서 다음 노드로 가는 가중치

                int newCost = nowCost + edgeCost; // "start -> now 비용" + "now -> nextNode 비용"
                if (dist[nextNode] > newCost) {  // 원래 알고 있던 최단 거리보다 방금 계산한 newCost가 더 작다면...
                    dist[nextNode] = newCost;  // 최단 거리 갱신
                    pq.offer(new Node(nextNode, newCost));  // 앞으로의 처리 대상 후보로 등록
                }
            }
        }

		// 시작 노드로부터 각 노드까지 가는 최소 비용이 담긴 배열 반환
        return dist;  
    }
}