[JAVA]플로이드-와샬(Floyd-Warshall) 알고리즘

플로이드-와샬?

모든 최단 경로를 구하는 방법, 음의 가중치 간선 가능

 

방법

Step 1. D[][] : 자기자신으로의 인접이 아니고 갈 수 없는 경로라면 INF

Step 2. k 경 i 출 j 도 : 경유지와 도착지가 같거나 출발지와 도착지가 같다면 패스

Step 3. 출발지에서 도착지까지의 가중치의 합이 경유지를 들렸을 때값보다 클 경우 갱신

 

 

소스 코드

import java.util.Scanner;

public class FloydTest {

	static final int INF = 9999999;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] D = new int[N][N];
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				D[i][j] = sc.nextInt();
				if(i != j && D[i][j] == 0) { // 자기 자신으로의 인접이 아니고 갈수 없다면
					D[i][j] = INF;
				}
			}
		}
		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(j==k || i==j) continue; // 경유지와 도착지가 같거나 출발지와 도착지가 같다면 패스
					if(D[i][k]+D[k][j] < D[i][j]) {
						D[i][j] = D[i][k]+D[k][j];
					}
				}
			}
		}
		System.out.println();
		
	}
}