플로이드 와샬 알고리즘

모든 정점에서 모든 정점으로 가는 최단 경로를 구하는 알고리즘.

 

public class Main{
	static int number = 6;
	static int INF = 1000000000;
	static int[][] arr = {
			{0, 10, 2, INF, INF, INF},
			{10, 0, 20, 30, INF, INF},
			{2, 20, 0, 5, 16, 15},
			{INF, 30, 5, 0, INF, 40},
			{INF, INF, 16, INF, 0, 42},
			{INF, INF, 15, 40, 42, 0}
	};
	static int d[][] = new int[number+1][number+1]; //최단 거리
	
	public static void floydWarshall() {
		// 변수 초기화 
    	for(int i=0; i<number; i++) {
    		for(int j=0; j<number; j++) {
    			d[i][j] = arr[i][j];
    		}
    	}
    	
    	// k = 거쳐가는 노드
    	for(int k=0; k<number; k++) {
    		//i = 출발 노드
    		for(int i=0; i<number; i++) {
    			// j = 도착 노드
    			for(int j=0; j<number; j++) {
    				// 거쳐가는 비용이 직접 가는 비용보다 더 적을 때
    				if(d[i][k] + d[k][j] < d[i][j]) {
    					d[i][j] = d[i][k] + d[k][j];
    				}
    			}
    		}
    	}
	}
    public static void main(String[] args) throws Exception {
    	Scanner sc = new Scanner(System.in);
    	
    	floydWarshall();
    	
    	for(int i=0; i<number; i++) {
    		for(int j=0; j<number; j++) {
    			System.out.print(d[i][j] + " ");
    		}
    		System.out.println();
    	}
    }
}
=========================================================================
0 10 2 7 18 17 
10 0 12 17 28 27 
2 12 0 5 16 15 
7 17 5 0 21 20 
18 28 16 21 0 31 
17 27 15 20 31 0