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

개요

플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 효율적으로 구하는 알고리즘이다. 다익스트라나 벨만-포드와 달리 단일 시작점이 아닌 전체 정점 간의 경로를 계산하며, 동적 계획법(Dynamic Programming) 기반으로 3중 반복문을 통해 구현된다. 네트워크 분석, 지도 서비스, 경로 최적화 등에서 광범위하게 활용된다.

---

1. 개념 및 정의

Floyd-Warshall 알고리즘은 가중치가 있는 방향 그래프에서 정점 i에서 j로 가는 최단 거리 d[i][j]를, 중간 정점 k를 거쳐 최적화해 나가는 방식이다. 음수 가중치는 가능하나, 음수 사이클은 허용되지 않는다.

---

2. 알고리즘 동작 원리

단계	설명
1단계	거리 행렬 d[i][j]를 초기화 (자기 자신은 0, 없으면 ∞)
2단계	모든 정점 k에 대해 다음을 반복
3단계	모든 i, j쌍에 대해 d[i][j] = min(d[i][j], d[i][k] + d[k][j])

k를 중간 경유지로 고려해 최단 거리를 반복적으로 갱신한다.

---

3. 파이썬 구현 예시

def floyd_warshall(graph):
    V = len(graph)
    dist = [row[:] for row in graph]  # 깊은 복사

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# INF = float('inf') 로 정의 후, graph[i][j]에 가중치 입력

이 알고리즘은 단순하면서도 강력한 최단 거리 계산 알고리즘이다.

---

4. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(V³)
공간 복잡도	O(V²)

모든 정점 쌍에 대해 세 번의 반복이 필요하므로 소규모/중간 규모 그래프에 적합하다.

---

5. 다익스트라/벨만포드와 비교

항목	플로이드-워셜	다익스트라	벨만-포드
목적	모든 정점 쌍 간 최단 경로	단일 시작점 최단 경로	단일 시작점 + 음수 간선 가능
음수 간선	가능	불가능	가능
음수 사이클 탐지	불가능 (별도 처리 필요)	불가능	가능
시간 복잡도	O(V³)	O((V+E)logV)	O(VE)

다익스트라는 빠르고, 벨만-포드는 유연하며, 플로이드는 전체 분석에 강하다.

---

6. 활용 사례

분야	적용 예시
교통/물류	모든 지점 간 거리 계산, 물류 센터 최적화
네트워크 최적화	라우팅 테이블 초기화 및 거리 분석
GIS 시스템	지도 경로 분석 및 거리 계산
그래프 분석	연결성 및 경로 분석, 최소 거리 기반 클러스터링
알고리즘 문제풀이	경유지 포함 최단 거리, 사이클 분석 문제 등

특히 정점 수가 100 이하인 문제에서는 매우 효과적이다.

---

7. 결론

Floyd-Warshall 알고리즘은 모든 정점 간 최단 경로를 계산하는 데 특화된 동적 계획법 기반 알고리즘으로, 정점 수가 많지 않은 상황에서 매우 유용하다. 단순한 코드 구조에도 불구하고 높은 신뢰성과 정확도를 자랑하며, 음수 간선도 허용되어 복잡한 그래프 구조 분석에 유리하다. 다양한 실전 문제 및 시스템에서 그 활용성이 매우 높다.