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

플로이드 워셜(Floyd-Warshall)에 대해 공부 후 정리하였습니다.

1️⃣ 개념

다이나믹 프로그래밍 기반의 최단 경로 알고리즘으로 그래프 내 모든 정점 쌍 (i, j) 사이의 최단 거리를 구함.
다익스트라가 한 정점에서 출발하는 최단 경로를 구하는 것과 달리, 플로이드-워셜은 전체 쌍을 고려한다.
음수 가중치 간선도 허용(단, 음수 사이클은 허용하지 않음).

2️⃣ 특징

• 모든 정점 쌍 최단 거리 계산 가능
• 음수 가중치 허용(음수 사이클 존재 시 경로 불가능)
• 구현이 매우 간단(3중 for문)
• DP적 성격 → dp[k][i][j] = 정점 집합 {1…k}만 거쳐서 i→j 가는 최단 거리

3️⃣ 시간 복잡도

O(N³)

• 따라서 N ≤ 400 정도에서 자주 쓰임 (백준에서 플로이드 관련 문제 대부분 N ≤ 400).
• 메모리 복잡도: O(N²)

4️⃣ 구현 방법

1. 초기화
   • 인접 행렬 dist[i][j] 생성
   • i == j → 0
   • 간선 존재 → 해당 가중치
   • 간선 없음 → INF(무한대)
2. 점화식 적용

   for (k = 1 ~ N)         // 거쳐가는 노드
     for (i = 1 ~ N)       // 출발 노드
    for (j = 1 ~ N)     // 도착 노드
      if (dist[i][j] > dist[i][k] + dist[k][j])
          dist[i][j] = dist[i][k] + dist[k][j]
   

   5️⃣ 기본 코드 (Java)

   ```java import java.util.*;

public class FloydWarshall { static final int INF = 1000000000; // 충분히 큰 값 static int n, m; static int[][] dist;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt(); // 정점 개수
    m = sc.nextInt(); // 간선 개수

    dist = new int[n+1][n+1];

    // 초기화
    for (int i = 1; i <= n; i++) {
        Arrays.fill(dist[i], INF);
        dist[i][i] = 0;
    }

    // 간선 입력
    for (int i = 0; i < m; i++) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        dist[a][b] = Math.min(dist[a][b], c); // 여러 간선 있을 수 있음
    }

    // 플로이드-워셜
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF) System.out.print("INF ");
            else System.out.print(dist[i][j] + " ");
        }
        System.out.println();
    }
} } ```

경로 복원

• 최단 거리 값뿐만 아니라 실제 경로를 추적하려면, next[i][j] 배열을 둔다
• next[i][j] = j (i→j 직접 연결일 때)로 초기화
• 업데이트할 때 경유지 k를 통해 최단 거리가 줄어들면 next[i][j] = next[i][k] ```java int[][] next = new int[n+1][n+1];

// 초기화 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) next[i][j] = i; else if (dist[i][j] < INF) next[i][j] = j; else next[i][j] = -1; } }

// 플로이드-워셜 중 갱신 if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; next[i][j] = next[i][k]; }

// 경로 복원 함수 List getPath(int u, int v) { if (next[u][v] == -1) return new ArrayList<>(); List path = new ArrayList<>(); path.add(u); while (u != v) { u = next[u][v]; path.add(u); } return path; } ```

7️⃣ 자주 사용하는 곳

• 모든 정점 쌍 최단 거리 필요할 때 (네트워크, 물류 최적 경로, 도시 간 최단 거리)
• 그래프 크기가 작을 때 (N ≤ 400 정도)
• 음수 가중치 간선이 포함될 수 있을 때 (다익스트라는 음수 간선 불가능하지만 플로이드-워셜은 가능)