최단 경로 찾기 (Floyd-Warshall)

플로이드 워셜 알고리즘

1. 모든 정점간의 최단 거리 찾기
2. 한 정점(k)에 대해 i에서 j까지 이 정점을 거쳐가는 모든 경로를 탐색
3. 이 정점을 거쳐가는 경우가 기존 경로보다 짧은 경우 업데이트
4. O(N^3)

N이 작게 주어진다면!!

static int[][] dist =new int[V][V];

static void floyd() {
    for(int k=0; k<V; k++) {
    	for(int i=0; i<V; i++) {
            for(int j=0; j<V; j++) {
            	if(dist[i][j] > dist[i][k] + dist[k][i]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}