플로이드 워셜 알고리즘

플로이드 워셜 알고리즘이란?

가중치가 있는 방향/무방향 그래프에서 모든 정점 쌍 사이의 최단 거리를 한번에 구하는 DP 기반 알고리즘

음수 가중치 간선은 허용하지만, 음수 사이클이 있으면 최단거리가 정의되지 않는다.

시간 공간 복잡도

시간 : O(N^3)

공간 : O(N^2)

핵심 아이디어

dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])

 

해석 : i → j 까지 가는 가장 짧은 값을 출력

i → k → j 가 가능하다면 해당 값으로 값을 대체

❗반복문의 순서가 중요하다 k → i → j

중간 정점으로 1..k만 허용 하는 부분 문제를 누적해야 하므로 이 순서가 무조건 보장 되어야한다.

사용 판단 기준

1. N이 중간 규모 대략 N≤500 이고 모든 쌍의 거리 도달성을 한번에 알고 싶을 때,
2. 그래프가 간선이 많아 다익스트라 알고리즘을 N번 돌리는 이점이 적을 때,

반대로 노드가 500 이상이고 그래프간의 간선이 적으면 다익스트라 * N 알고리즘 이나 존슨 알고리즘이 더 좋다.

풀이 방법

import java.io.*;
import java.util.*;

public class FloydWarshall {
    static final long INF = (long)1e15; // 합 연산 대비 넉넉한 INF (int 오버플로 방지)
    static int N, M;
    static long[][] dist;
    static int[][] next; // 경로 복원용 (i->j 최단경로에서 i 다음 노드)

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine().trim());
        M = Integer.parseInt(br.readLine().trim());

        dist = new long[N+1][N+1];
        next = new int[N+1][N+1];

        // 1) 초기화
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
        
        // 2) 간선 입력 (다중 간선 -> 더 작은 가중치만)
        for (int e = 0; e < M; e++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            if (w < dist[a][b]) {
                dist[a][b] = w;
                next[a][b] = b; // 바로 가는 간선이면 경로복원 시작점
            }
        }
        
        // 3) 핵심 3중 루프 (k -> i -> j)
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    long nd = dist[i][k] + dist[k][j];
                    if (nd < dist[i][j]) {
                        dist[i][j] = nd;
                        next[i][j] = next[i][k]; // 경로복원 포인트
                    }
                }
            }
        }
        // 4) 음수 사이클 검사: dist[i][i] < 0 이면 i에서 i로 음수사이클
        boolean hasNegCycle = false;
        for (int v = 1; v <= N; v++) {
            if (dist[v][v] < 0) { hasNegCycle = true; break; }
        }

        // 출력 or 사용 예시
        System.out.println("hasNegCycle = " + hasNegCycle);
        // 예: 1->5 최단거리와 경로
        int s = 1, t = 5;
        if (dist[s][t] >= INF/2) {
            System.out.println("unreachable");
        } else {
            System.out.println("dist = " + dist[s][t]);
            System.out.println("path = " + getPath(s, t));
        }
    }
    
    // 경로 복원 (next 배열 사용)
    static List<Integer> getPath(int u, int v) {
        if (next[u][v] == 0) return Collections.emptyList();
        List<Integer> path = new ArrayList<>();
        path.add(u);
        while (u != v) {
            u = next[u][v];
            if (u == 0) return Collections.emptyList(); // 방어적
            path.add(u);
        }
        return path;
    }
}

마무리 요약

• 플로이드–워셜은 간단한 코드로 모든 쌍 최단거리/도달성/경로를 한 번에 해결한다.
• N이 중간 규모(500), 여러 질의가 있거나 행렬 변형 응용이 필요할 때 사용