[알고리즘 / JAVA] 플로이드-워셜(Floyd-Warshall) 완전 정복 – 모든 정점 간 최단 거리

heon.blog·2025년 6월 2일

알고리즘

알고리즘 / JAVA

목록 보기

5/8

1. 개요

플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점에서 모든 정점까지의 최단 거리를 구할 수 있는 알고리즘입니다.

다익스트라는 단일 시작점에서 출발하는 최단 거리만 구할 수 있고,
벨만-포드는 음수 간선과 사이클 탐지에 유용하지만 단일 시작점 기준입니다.

반면, 플로이드-워셜은 모든 정점 쌍 간의 최단 거리를 구할 수 있어 그래프 내 모든 경로 정보를 필요로 하는 문제에서 효과적입니다.

입력 그래프가 정점 수가 적고 간선 수가 많을 때 적합합니다.
간선에 음수 가중치는 허용되지만, 음수 사이클은 허용되지 않습니다.

2. 플로이드-워셜이란?

플로이드-워셜은 ‘모든 정점 쌍 사이의 최단 거리’를 한 번에 구하는 방법입니다.
각 정점을 거쳐 가는 경로를 차례대로 확인하면서 최단 거리를 갱신해 나가는 방식으로 동작합니다.

출처: medium.com - Understanding Floyd-Warshall Algorithm

다음은 그림에 대한 동작 과정입니다.

4 x 4 크기의 dist[][] 배열을 INF 값으로 초기화합니다.
자기 자신으로 가는 비용을 0으로 설정합니다.

dist[i][i] = 0;

k, i, j 세 정점을 잡고, 현재 i → j로 가는 최단 거리보다 i → k + k → j를 거쳐 가는 경로가 더 짧다면, 해당 경로로 최단 거리를 갱신합니다.

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

이 과정을 k = 1 ~ n까지 모든 정점에 대해 반복하면, 최종적으로 모든 정점 쌍 간의 최단 거리가 dist[][] 배열에 저장됩니다.

3. 플로이드-워셜 구현 (Java)

import java.util.*;

public class FloydWarshallExample {
    static final int INF = Integer.MAX_VALUE / 2; // Integer.MAX_VALUE 사용하면 overflow 위험 존재

    public static void main(String[] args) {
        int n = 4; // 정점 수
        int[][] dist = new int[n][n];

        // 초기화
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0; // 자기 자신으로 가는 비용은 0
        }

        // 간선 정보 (예시: 단방향)
        // 같은 간선의 정보가 여러 개일 경우 최솟값 반영
        dist[0][1] = 1;
        dist[1][2] = 3;
        dist[0][2] = 2;
        dist[2][3] = -2;

        // 알고리즘 실행
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print((dist[i][j] == INF ? "INF" : dist[i][j]) + " ");
            }
            System.out.println();
        }
    }
}

3-1. 구현 핵심 요약

플로이드-워셜 알고리즘을 구현할 때 핵심이 되는 흐름은 다음과 같습니다.

dist[i][j] 배열을 만들어, 정점 i에서 j로 가는 최단 거리를 저장합니다.
초기에는 i에서 j로 가는 간선이 있다면 그 가중치로, 없다면 충분히 큰 값(INF)으로 설정합니다.
여기서 INF 값으로 Integer.MAX_VALUE를 사용하면 덧셈 과정에서 오버플로우가 발생할 수 있으므로,
INF는 Integer.MAX_VALUE / 2 정도로 큰 값으로 사용합니다.
세 정점 i, j, k를 잡고, 정점 k를 거쳐 i에서 j로 가는 경로가
현재 알고 있는 최단 거리보다 더 짧은지 확인하면서 거리를 업데이트합니다.
이 과정을 다음과 같은 식으로 표현할 수 있습니다:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
위 작업을 모든 정점 쌍 (i, j)에 대해, 그리고 모든 정점 k에 대해 반복합니다.

이 과정을 통해, 모든 정점 쌍 간의 최단 거리를 효율적으로 구할 수 있으며, 음수 가중치가 있어도 동작한다는 장점이 있습니다.

4. 다익스트라 vs 벨만-포드 vs 플로이드-워셜

항목	다익스트라	벨만-포드	플로이드-워셜
출발점	단일	단일	모든 정점 쌍
음수 가중치	X	O	O
음수 사이클 탐지	X	O	O (`dist[i][i] < 0 체크`)
시간 복잡도	O((V + E) log V)	O(V × E)	O(V³)
적합한 그래프	희소 그래프	음수 포함 그래프	정점 수 적고 간선 많은 그래프

5. 백준 문제 추천

사이트	문제명	설명
백준 11404	플로이드	기본적인 모든 쌍 최단 거리 문제
백준 1956	운동	음수 사이클 검출 (플로이드-워셜 응용)
백준 11780	플로이드 2	경로 복원