[JAVA]다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘이란? 

=> 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (간선들은 모두 양의 간선이어야 한다)

=> 정점 A와 정점 B를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로

 

 

방법

Step1. 미방문 정점 중 최적 비용이 최소인 것 찾기

Step2. 선택 정점 방문하고 경유지로 고려하여 미방문정점들로 가는 최적비용을 최적화

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DijkstraTest {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());// 정점수
		int[][] input = new int[N][N];
		
		StringTokenizer st=null;
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < N; ++j) {
				input[i][j] = Integer.parseInt(st.nextToken());
			}
		}// 인접행렬 생성
		int start = 0, end = N-1;
		int[] distance = new int[N];
		int[] path = new int[N];
		boolean[] visited = new boolean[N];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[start] = 0;
		
		int min = Integer.MAX_VALUE,minIndex=0;
		for (int i = 0; i < N; ++i) {
			 min = Integer.MAX_VALUE;
			//step1. 미방문정점 중 최적비용이 최소인 정점 찾기
			for (int j = 0; j < N; ++j) {
				if(!visited[j] && distance[j] < min) {
					min = distance[j];
					minIndex = j;
				}
			}		
			//step2. 선택정점 방문하고 경유지로 고려하여
			//		  미방문정점들로 가는 최적비용을 최적화
			visited[minIndex] = true;
			if(minIndex == end) break;
			
			for (int j = 0; j < N; ++j) {
				if(!visited[j] && input[minIndex][j] != 0
						&& min + input[minIndex][j] < distance[j]) {
					distance[j] = min+ input[minIndex][j];
					path[j] = minIndex;
				}
			}
			
		}
		System.out.println(distance[end]);
		System.out.println(Arrays.toString(path));		
	}

}

 

 

소스코드2  (우선순위큐, 연결리스트 사용)

package BOJ;

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

public class BOJ_10282_해킹_Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int n = Integer.parseInt(st.nextToken()); // 컴퓨터 개수
			int d = Integer.parseInt(st.nextToken()); // 의존성 개수
			int c = Integer.parseInt(st.nextToken())-1; // 해킹당한 컴퓨터의 번호 (1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n)
			List<int[]> list[] = new ArrayList[n];
			for (int i = 0; i < n; i++) {
				list[i] = new ArrayList<int[]>();
			}
			
			for (int i = 0; i < d; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int a = Integer.parseInt(st.nextToken())-1;
				int b = Integer.parseInt(st.nextToken())-1;
				int s = Integer.parseInt(st.nextToken());
				list[b].add(new int[] {a,s});
			}
			
			PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o1[1]-o2[1];
				}
			});
			
			int[] path = new int[n];
			Arrays.fill(path, Integer.MAX_VALUE);
			path[c] = 0;
			pq.offer(new int[] {c, 0});
			while(!pq.isEmpty()) {
				int[] cur = pq.poll();
				int now_num = cur[0];
				int now_val = cur[1];
				for (int i = 0; i < list[now_num].size(); i++) {
					int[] next = list[now_num].get(i);
					int next_num = next[0];
					int next_val = next[1];
					if(path[next_num]>now_val+next_val) {
						path[next_num]=now_val+next_val;
						pq.offer(new int[] {next_num, path[next_num]});
					}
				}
			}
			
			int ans1 = 0; // 총 감염되는 컴퓨터 수
			int ans2 = 0; // 마지막 컴터가 감염되기 까지 걸리는 시간
			for (int i = 0; i < n; i++) {
				if(path[i]!=Integer.MAX_VALUE) ans1++;
				if(path[i]!=Integer.MAX_VALUE&&ans2<path[i]) ans2=path[i];
			}
			
			System.out.println(ans1+ " "+ans2);
		}
	}
	
}