Java | Dijkstra (최단 경로)

같이 풀면 좋은 문제

 

https://www.acmicpc.net/problem/24042

 

다익스트라 알고리즘

- 최단 경로를 위해 사용

- 현재 코드는 우선순위 큐를 이용

- 가중치 값들이 모두 0보다 커야 한다.(음수일 경우에는 안됨)

 

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

public class DijkstraPqMain {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		// 인접 행렬로 만듦.
		int[][] g = new int[N][N];
		// MST에 속하면 true.
		boolean[] v = new boolean[N];
		int[] dist = new int[N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				g[i][j] = sc.nextInt();
			}
			dist[i] = Integer.MAX_VALUE;
		}

		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) ->
			Integer.compare(o1[1], o2[1])
		);
		// 0번 정점부터 MST에 시작
		dist[0] = 0;

		pq.offer(new int[] {0, dist[0]});

		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int minVertex = cur[0];
			int min = cur[1];
			if (v[minVertex]) continue; // 싸이클 방지
			
			v[minVertex] = true;
			
			if (minVertex == N-1) break;
			for (int j = 0; j < N; j++) {
				if (!v[j] && g[minVertex][j] != 0 && dist[j] > min + g[minVertex][j]) {
					dist[j] = min + g[minVertex][j];
					pq.offer(new int[] {j, dist[j]});
				}
			}
				
		}
		System.out.println(dist[N-1]);
		sc.close();
	}
}