[Algorithm] 플로이드-와샬 (Floyd-Warshall) | Java

📘 플로이드-와샬 알고리즘 정리

모든 노드 쌍 사이의 최단 거리를 구하는 알고리즘
음의 가중치가 있어도 동작하지만, 음의 사이클이 있으면 안 된다!

한 정점에서 다른 모든 정점까지 -> 다익스트라, 벨만-포드
모든 정점 쌍에 대해 -> 플로이드-와샬

---

⚙️ 동작 원리

플로이드-와샬은 다이나믹 프로그래밍 기반으로,

노드 i에서 j까지 가는 최단 경로는,
노드 k를 거쳐서 가는 경로가 더 짧을 수도 있다.

dist[i][j] = i에서 j까지 가는 최소 거리일 때,

3중 반복문을 돌면서
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])로 갱신

핵심은 “i → j로 가는 경로에 k를 경유해 보는 것”

🚨 3중 반복문을 돌릴 때 k를 바깥에 둬야 한다.
k는 경유할 노드이기 때문에, 매번 k에 대해 전체 맵을 갱신해야 한다.

---

✅ 예제 코드 (Java)

final int INF = 999_999_999;

// 초기화
int[][] dist = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
    	// 자기 자신은 0
        if (i == j) {		
        	dist[i][j] = 0;
            
        // 나머지 INF
		} else {			
        	dist[i][j] = INF;
        }
    }
}

// 간선 입력
for (int i = 0; i < e; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int cost = Integer.parseInt(st.nextToken());
	
    // 최소 비용 저장
    dist[a][b] = Math.min(dist[a][b], cost);
    dist[b][a] = Math.min(dist[b][a], cost);

}

// 플로이드-와샬
for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
        	// i -> j 비용과 i -> k -> j 비용을 비교하여 갱신
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

🔁 동작 풀이

1. 거리 값에 대한 배열 dist[][]를 초기화 한다.

2. 자기 자신은 0, 연결된 간선은 가중치로, 나머지는 무한대 (INF) 값을 넣어준다.

   2-1. 특정 노드로 가는 경로가 하나가 아니라면, 그 중 최소 비용을 저장한다.

3. 1부터 N까지 모든 노드 k에 대해:

   i, j를 각각 1~N까지 순회하며

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 수행하여 비용을 갱신해준다.

---

사용 상황

• 모든 정점 쌍의 최단 거리가 필요한 경우

• 정점 개수가 적고(보통 N ≤ 500 이하) 간선이 많거나 전체 경로가 자주 바뀌지 않는 경우

• 음수 가중치 간선이 있는 경우

예시

• 도시 간 최소 이동 거리 구하기

• 비용이 다른 환승 경로 최적화

• 네트워크 지연 시간 계산

---

주의할 점

음의 사이클이 존재하면 사용하면 안 됨 (무한 루프 가능)

메모리 복잡도: O(N^2) / 시간 복잡도: O(N^3)

대체로 N <= 500 이하에서 사용 (그 이상은 시간 초과 위험)