Dijkstra 알고리즘 (최단 경로 탐색)

출발 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘

특징

• 한계: 음의 간선은 포함되지 않음.
• 알고리즘: 그리디 알고리즘과 동적 계획법의 결합.
• 시간 복잡도: O(E log V) (E: 간선의 수, V: 노드의 수)

작동 과정

1. 출발 노드 설정
   출발 노드를 설정합니다.

2. 최소 비용 저장
   출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다. 출발 노드는 0으로, 나머지 노드는 INF = 10^9로 초기화합니다.

3. 가장 비용이 적은 노드 선택 (그리디)
   방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택합니다.

4. 최소 비용 갱신 (DP)
   해당 노드를 거쳐 특정 노드로 가는 최소 비용을 갱신합니다.

5. 반복
   모든 노드가 처리될 때까지 3~4번을 반복합니다.

인접 리스트 & 우선순위 큐 구현

인접 리스트로 그래프 초기화

List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i < V + 1; i++) {
	graph.add(new ArrayList<>());
}

for (int i = 0; i < E; i++) {
	graph.get(u).add(new Node(v, w));
}

우선순위 큐 사용

우선순위 큐의 정렬 기준을 최단 거리의 오름차순으로 지정하면, 항상 최단 거리를 가진 노드를 우선적으로 처리할 수 있습니다.

PriorityQueue<Node> pq = new PriorityQueue<>();

static class Node implements Comparable<Node> {
	int idx, cost;

	Node(int idx, int cost) {
		this.idx = idx;
		this.cost = cost;
	}

	@Override
	public int compareTo(Node o) { // 오름차순 정렬
		return Integer.compare(this.cost, o.cost);
	}
}

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {

	// 노드 클래스 : 노드 번호, 가중치 저장
	static class Node implements Comparable<Node> {
		int idx, cost;

		Node(int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) { // 오름차순 정렬
			return Integer.compare(this.cost, o.cost);
		}
	}

	public static void main(String[] args) {
		// 그래프 입력 (인접 리스트) => V+1 크기
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt();
		int E = sc.nextInt();
		int start = sc.nextInt();

		List<List<Node>> graph = new ArrayList<>();
		for (int i = 0; i < V + 1; i++) {
			graph.add(new ArrayList<>());
		}

		for (int i = 0; i < E; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			graph.get(u).add(new Node(v, w));
		}

		// 최단 거리 배열 초기화
		int[] dist = new int[V + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;

		// 우선순위 큐 초기화
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(start, 0));

		// 모든 노드 방문할 때까지 반복
		while (!pq.isEmpty()) {
			Node currNode = pq.poll();

			// 현재 노드의 비용이 높으면 방문 필요 X
			if (dist[currNode.idx] < currNode.cost)
				continue;

			// 모든 인접 노드 확인
			for (Node nextNode : graph.get(currNode.idx)) {
				int newDist = currNode.cost + nextNode.cost;

				// 현재보다 최단 경로 발견 시 갱신
				if (dist[nextNode.idx] > newDist) {
					dist[nextNode.idx] = newDist;
					pq.offer(new Node(nextNode.idx, newDist));
				}
			}
		}

		// 결과 출력
		for (int i = 1; i < V + 1; i++) {
			if (dist[i] == Integer.MAX_VALUE)
				System.out.println("INF");
			else
				System.out.println(dist[i]);
		}
	}
}