1. 최단 경로의 정의

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

2. 하나의 시작 정점에서 끝 정점까지의 최단 경로 알고리즘

1) 다익스트라 알고리즘

음의 가중치를 허용하지 않는다.

2) 벨만 포드 알고리즘

음의 가중치를 허용한다.

3. 다익스트라 알고리즘

시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단경로를 구하는 방식

📝소스코드

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

/*
5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 8 6 5 0

output==> 8
*/

public class 다익스트라 {
	
	static int N, INF = Integer.MAX_VALUE;
	static int[] dis;
	static int[][] matrix;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		matrix = new int[N][N];
		dis = new int[N];
		visited = new boolean[N];
		Arrays.fill(dis, INF);
		
		StringTokenizer st = null;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dis[0] = 0;
		int min = 0;
		int current = 0;
		while(true) {
			min = INF;
			// 1단계. 방문하지 않은 정점들 중 출발지에서 자신까지 오는 비용이 최단인 정점을 선택
			for(int i=0; i<N; i++) {
				if(visited[i]) continue;
				if(min > dis[i]) {
					// 최소인 정점 정보를 저장
					min = dis[i];
					current = i;
				}
			}
			
			visited[current] = true;
			if(current == N-1) break;
			
			//2단계. 선택된 정점을 경유지로 하는 거리 정보 업데이트
			for(int i=0; i<N; i++) {
				if(visited[i] || matrix[current][i] == 0) continue;
				// min => dis[current]
				dis[i] = Math.min(dis[i], matrix[current][i] + min);
			}
		}
		
		System.out.println(dis[N-1]);
	
	}

}

Priority Queue Version

public class 다익스트라 {
	
	static int N, INF = Integer.MAX_VALUE;
	static int[] dis;
	static int[][] matrix;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		matrix = new int[N][N];
		dis = new int[N];
		visited = new boolean[N];
		Arrays.fill(dis, INF);
		
		StringTokenizer st = null;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// index, weight
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		
		pq.add(new int[] {0,0});
		while(true) {
			// 1단계. 방문하지 않은 정점들 중 출발지에서 자신까지 오는 비용이 최단인 정점을 선택
			int[] cur = pq.poll();
			int curidx = cur[0];
			int minWeight = cur[1];
			if(visited[curidx]) continue; 	//이미 최소값으로 처리된 정점 
			
			dis[curidx] = minWeight;
			visited[curidx] = true;
			if(curidx == N-1) break;
			
			//2단계. 선택된 정점을 경유지로 하는 거리 정보 업데이트
			for(int i=0; i<N; i++) {
				if(visited[i] || matrix[curidx][i] == 0) continue;
				// min => dis[current]
				dis[i] = Math.min(dis[i], matrix[curidx][i] + minWeight);
				pq.add(new int[] {i,dis[i]});
			}
		}
		
		System.out.println(dis[N-1]);
	
	}

}