다익스트라 알고리즘

다익스트라 알고리즘

하나의 시작 정점에서 끝 정점까지의 최단 경로이다.
음의 가중치를 허용하지 않는 최단경로 알고리즘임

다익스트라 슈도코드
s : 시작정점
A : 인접행렬
D : 시작정점에서의 거리 
v : 정점 집합
U : 선택된 정점 집합
Dijkstra(s, A, D){
 U = {s};
 
 for 모든 정점 v
  D[v] <- A[s][v]
  
 While U != V
 	D[w] 가 최소인 정점 w 를 선택한다 (단 w = V - U)
    U <- U u {w}
    For w에 인접한 모든 미방문 정점 v
    	D[v] <- min(D[v], D[w] + A[w][v])
}     

package test;

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

public class dijkstraTest {

	static int adj[][]; // 인접행렬
	static int N; // 정점 수 
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		adj = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				adj[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 인접행렬 완성 
		
		Dijkstra(0);
	}

	public static void Dijkstra(int sNode) {
		int[] distance = new int[N]; // 시작노드로부터 각 노드까지의 최소비용
		boolean[] visited = new boolean[N]; // 시작노드로부터 각 노드까지의 최소비용이 확정났는가를 판단해주는 배열
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[sNode] = 0; // 시작노드를 0으로 초기화

		for (int i = 0; i < N; i++) {
			// (시작노드로부터의)최소비용이 확정나지 않은 노드를 중에 가장 거리가 짧은 노드선택하기
			int minDist = Integer.MAX_VALUE;
			int minNode = -1;
			for (int j = 0; j < N; j++) {
				if(!visited[j]) {
					if(minDist > distance[j]) {
						minDist = distance[j];
						minNode = j;
						visited[minNode] = true;
					}
				}
			}
			// 거리가짧은 노드가 선택되었다면
			// 그 노드를 경유하는것을 고려하여 시작노드로부터의 최소비용을 업데이트 하기 
			for (int j = 0; j < N; j++) {
				if(!visited[j] && adj[minNode][j] != 0) {
					if(distance[j] > distance[minNode] + adj[minNode][j]) {
						distance[j] = distance[minNode] + adj[minNode][j];
					}
				}
			}
		}
		
		System.out.println(Arrays.toString(distance));

	}

}