[Algorithm] 플로이드-워셜 알고리즘

플로이드-워셜 (Floyd-Warshall) 알고리즘

모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘!
(즉, 모든 정점이 연결되어있는지 플로이드 워셜 알고리즘을 통해 확인할 수 있다. -> 모든 쌍의 경로 존재 여부 파악)
거쳐가는 정점을 기준으로 알고리즘을 수행한다.
시간복잡도가 O(n^3)이기 때문에 노드의 개수 1000개 미만인지 확인!

Algorithm-Step

1. D[i][j] : 정점i에서 정점j로의 최소비용, 자기자신으로의 인접이 아니고 갈 수 없는 경로라면 INF
2. k 경유지 i 출발지 j 도착지 : 경유지와 도착지가 같거나 출발지와 도착지가 같다면 패스
3. 출발지에서 도착지까지의 가중치의 합이 경유지를 들렸을 때값보다 클 경우 갱신

Code

import java.util.Scanner;

/*
5
0 4 2 5 0
0 0 1 0 4
1 3 0 1 2
-2 0 0 0 2
0 -3 3 1 0


5
0 4 2 5 0
0 0 1 0 4
1 3 0 1 2
2 0 0 0 2
0 3 3 1 0
*/
/**
 * @author taeheekim
 */
public class Floyd {

	static final int INF = 9999999;
	static int N,adjMatrix[][];
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		adjMatrix = new int[N][N];
		for(int i=0; i<N; ++i) {
			for(int j=0; j<N; ++j) {
				adjMatrix[i][j] = sc.nextInt();
				if(i != j && adjMatrix[i][j]==0) {//자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
					adjMatrix[i][j]=INF;
				}
			}
		}
		System.out.println("===========입력==========");
		print();
        // 출발지-->경유지-->목적지로 3중 루프 돌리면 오답
        // 경유지-->출발지-->목적지로 3중 루프 돌려야 정답
		for(int k=0; k<N; ++k) {
			for(int i=0; i<N; ++i) {
				if(i==k) continue; // 출발지와 경유지가 같다면 다음 출발지
				for(int j=0; j<N; ++j) {
					if(i==j || k==j) continue; // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 패스
					if(adjMatrix[i][j] > adjMatrix[i][k]+adjMatrix[k][j]) {
						adjMatrix[i][j] = adjMatrix[i][k]+adjMatrix[k][j];
					}
				}
			}
			print();
		}
	
	}
	private static void print() {
		for(int i=0; i<N; ++i) {
			for(int j=0; j<N; ++j) {
				System.out.print(adjMatrix[i][j]+"\t");
			}
			System.out.println();
		}
		System.out.println("=====================================");
		
	}

}

다익스트라와 플로이드-워셜의 차이점?

다익스트라 알고리즘은 어떠한 정점을 기준으로 잡고 다른 모든 정점으로의 최단 거리를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다!
문제를 풀때 기준점이 정해져있다면 다익스트라를, 그것이 아니라 모든 정점의 최단 거리를 구하거나 모든 쌍의 경로가 존재하는지 여부를 파악하는 문제라면 플로이드-워셜 문제를 푸는 것이 좋을 것 같다!