플로이드-와샬 알고리즘 (Floyd's Algorithm)

Floyd's Algorithm 이란?

 

- 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘

   (모든 정점에 대하여 각 정점의 최단거리를 모두 구한다.)

 

- i -> j 로 가는 최단거리를 구하기 위해 ① i->j    ② i -> k -> j 의 두 가지 경우의 최소값을 최단거리로 정한다.

  즉, 거쳐가는 정점을 기준으로 최단거리를 구한다.

 

- 시간복잡도 : O(n^3) 

 

- DP 이용

 

 

 

 

Floyd's Algorithm 이용 -  1) 최단거리 배열 D 구하기

public static void main(String arg[]){
	int n = 4;
    int[][] W = {{0,10,15,20},{5,0,9,10},{6,13,0,12},{8,8,9,0}; // 가중치 배열
    int[][] D = new int[n][n]; // 최단거리 배열
    
    floyd(4, W, D);
}

/*
    i->j 의 최단거리 구하는 함수
    1) i->j : i에서 j로 다이렉트로 가는 경우
    2) i->k->j : i에서 k를 거쳐 j로 가는 경우
    두 가지 경우 중 최소값을 최단거리로 판단하여 D[i][j]값으로 정한다.
*/
private static void floyd(int n, int[][] W, int[][] D){
	D = W; // 최단거리 배열 초기화(W=D)
	for(int k=0; k<n; k++){
    	for(int i=0; i<n; i++){
        	for(int j=0; j<n; j++){
            	Math.min(D[i][j], D[i][k]+D[k][j]);
            }
        }
    }
}

 

 

 

Floyd's Algorithm 이용 -  2) 최단경로 상에 놓여 있는 정점 구하기

public static void main(String arg[]){
	int n = 4;
    int[][] W = {{0,10,15,20},{5,0,9,10},{6,13,0,12},{8,8,9,0}; // 가중치 배열
    int[][] D = new int[n][n]; //최단거리 배열
    int[][] P = new int[n][n]; //최단경로에 포함된 인덱스가 가장 큰 정점 나타내는 배열
    
    floyd(4, W, D, P);
}

/*
    i->j 의 최단거리 구하는 함수
    1) i->j : i에서 j로 다이렉트로 가는 경우
    2) i->k->j : i에서 k를 거쳐 j로 가는 경우
    두 가지 경우 중 최소값을 최단거리로 판단하여 D[i][j]값으로 정한다.
    
    만약 i->k->j 가 최소값일 경우, 이때 k는 최단경로에 포함된 정점이다.
    k=0~n-1 중 최단경로에 포함된 k값 중 가장 큰 값을 P[i][j]에 저장한다.
    P[i][j]==0 인 경우는 i->j의 최단경로에 k값이 존재하지 않는다. 즉 최단경로는 i->j 이다.
*/
private static void floyd2(int n, int[][] W, int[][] D, int[][] P){
	D = W; // 최단거리 배열 초기화(W=D)
	for(int k=0; k<n; k++){
    	for(int i=0; i<n; i++){
        	for(int j=0; j<n; j++){
            	if(D[i][j] > D[i][k]+D[k][j]){
                	P[i][j] = k; 
                    D[i][j] = D[i][k]+D[k][j];
            	}
            }
        }
    }
}