다익스트라 알고리즘

package day12;

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

import com.sun.imageio.plugins.common.InputStreamAdapter;

public class Dijkstra {

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("dijkstra_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st= new StringTokenizer(br.readLine()," ");
		int V = Integer.parseInt(st.nextToken());
		int start = 0;
		int end = V-1;
		final int INFINITY = Integer.MAX_VALUE;
		int[][] matrix = new int[V][V];
		int[] distance = new int[V];
		boolean[] visited = new boolean[V];
		for (int i = 0; i < V; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < V; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		Arrays.fill(distance, INFINITY);
		
		distance[start] = 0;
		
		int min =0, current=0;
		for (int i = 0; i < V; i++) {
			min=INFINITY;
			for (int j = 0; j < visited.length; j++) {
				// 방문하지 않은정점이면서, 최소 가중치보다 작으면 업데이트
				if(!visited[j]&&distance[j]<min) {
					min=distance[j];
					current = j;
				}
			}
			visited[current]=true;
			// 선택 정점이 도착 정점이면 탈출
			if(current==end) {
				break;
			}
			for (int c = 0; c < V; c++) {
				// 방문하지 않은 정점이면서
				// 간선이 이어져 있고,
				// 경유지+가중치의 값이 distance의 저잔된 최소 가중치보다 작다면
				// 업데이트
				if(!visited[c] && matrix[current][c]!=0 && distance[c] > min + matrix[current][c]) {
					distance[c] = min + matrix[current][c];
				}
			}
		}
		System.out.println(distance[end]);
		
	}

}