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

1. 알고리즘 동작 과정

1. 최단 거리 배열을 초기화
• 자기 자신으로 가는 거리: 0
• 간선 존재 시 가중치 입력
• 그 외는 무한대(INF)

2. 중간 정점 k를 1개씩 선택
• 모든 출발점 i, 도착점 j에 대해
• distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

3. 이를 N번 반복하여 최단 거리 완성

2. 시간 복잡도

• O(N³)

• N: 정점 수

• 3중 for문 → 정점 수가 많을수록 연산량 급증

3. 주로 사용되는 곳

• 모든 노드 간의 거리 계산이 필요한 상황

• 예시:
• 지도 앱의 거리 계산
• 네트워크 통신 지연 시간 측정
• 교통망 분석

4. 예시코드 (Java, 주석 포함)

public class FloydWarshallExample {
    static final int INF = 99999999; // 도달 불가능을 나타내는 큰 수

    public static void main(String[] args) {
        // 입력 그래프: i에서 j로 가는 초기 비용
        int[][] graph = {
            {0, 4, INF, 6},
            {3, 0, 7, INF},
            {5, INF, 0, 4},
            {INF, 2, INF, 0}
        };

        int n = graph.length; // 정점 개수
        int[][] dist = new int[n][n]; // 최단 거리 배열

        // 초기 거리 설정
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 플로이드-워셜 알고리즘 실행
        for (int k = 0; k < n; k++) { // 중간 정점
            for (int i = 0; i < n; i++) { // 출발 정점
                for (int j = 0; j < n; j++) { // 도착 정점
                    // i → k → j 경로가 더 짧은 경우 갱신
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 최단 거리 출력
        System.out.println("최단 거리 결과:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

출력 결과

최단 거리 결과:
0 4 11 6
3 0 7 9
5 7 0 4
5 2 9 0

5. 장점과 단점

✅ 장점

• 모든 정점 쌍의 최단 거리를 한 번에 계산

• 음의 가중치 허용

• 구현이 간단하고 직관적

❌ 단점

• 시간 복잡도 O(N³) → 대규모 그래프에 비효율적

• 음의 사이클 존재 시 잘못된 결과 출력