플로이드-워셜 알고리즘: 모든 쌍 최단 경로의 전방위 탐색 가이드

다익스트라와 벨만-포드가 '한 지점'에서 출발하는 최단 경로를 구한다면, 플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프 내의 '모든 정점 쌍'에 대한 최단 거리를 한 번에 해결하는 강력한 도구입니다. 예를 들어 지하철 노선도의 모든 역 간 거리를 미리 계산해두거나, 소셜 네트워크의 모든 사용자 사이의 촌수를 파악할 때 이 알고리즘은 독보적인 편리함을 제공합니다. 본 포스팅에서는 플로이드-워셜의 동적 계획법적 원리와 3중 반복문의 매커니즘을 2,500자 이상의 기술적 분석으로 정리해 보겠습니다.

1. 플로이드-워셜의 핵심 원리: 거쳐가는 정점의 미학

플로이드-워셜 알고리즘의 아이디어는 '경유지'에 있습니다. 임의의 두 정점 $i$에서 $j$로 가는 최단 경로는, 중간에 어떤 정점 $k$를 거쳐가는 것이 더 빠른지, 아니면 기존의 경로가 더 빠른지를 비교하며 점진적으로 개선해 나가는 방식입니다. 이는 큰 문제를 작은 문제들의 해로 해결하는 동적 계획법(Dynamic Programming)의 전형적인 사례입니다.

1-1. 마법의 점화식 이해

알고리즘의 동작을 결정짓는 핵심 점화식은 다음과 같습니다. 각 단계 $k$마다 모든 정점 쌍 $(i, j)$에 대해 다음 연산을 수행합니다.

$D[i][j] = \min(D[i][j], D[i][k] + D[k][j])$

이 식은 "$i$에서 $j$로 바로 가는 비용"과 "$i$에서 $k$를 거쳐 $j$로 가는 비용" 중 더 짧은 거리를 선택하여 최단 거리 테이블을 업데이트한다는 의미를 내포하고 있습니다.

2. 3중 반복문 구조와 시간 복잡도의 특성

플로이드-워셜 알고리즘은 구현이 매우 직관적이라는 강력한 장점이 있습니다. 2차원 배열(인접 행렬)을 생성한 뒤, 3중 for문을 사용하여 모든 정점을 중간 정점으로 설정하며 거리를 업데이트합니다. 하지만 정점의 개수가 $V$일 때 $V \times V \times V$번의 연산이 수행되므로 시간 복잡도는 $O(V^3)$에 달합니다.

2-1. 적절한 사용 환경과 한계

$O(V^3)$의 복잡도는 노드 수가 많아질수록 기하급수적으로 연산량이 증가함을 의미합니다. 따라서 보통 노드 수가 500개 이하인 환경에서 가장 효과적으로 활용됩니다. 반면 노드 수는 많고 간선이 적은 희소 그래프에서는 다익스트라를 모든 노드에 대해 반복 수행하는 것이 더 유리할 수 있습니다. 하지만 플로이드-워셜은 코드가 매우 간결하여 실수할 확률이 낮다는 실무적인 이점이 있습니다.

3. 실무에서의 활용 및 음수 가중치 처리

플로이드-워셜 역시 벨만-포드와 마찬가지로 음수 가중치 간선이 포함되어 있어도 정상 동작합니다. 단, 음수 사이클이 있는 경우에는 정확한 값을 낼 수 없으므로 주의가 필요합니다. 실무에서는 버스 환승 경로 정보 시스템, 통신 네트워크의 라우팅 테이블 생성, 그리고 복잡한 선행 관계를 가진 데이터 구조의 연결성 확인(Transitive Closure) 등에 폭넓게 사용됩니다.

고급 팁: 연결 성분 확인하기

만약 가중치가 없는 그래프에서 단순히 "두 노드가 연결되어 있는가?"만 알고 싶다면, $\min$ 연산 대신 논리 연산($OR$)을 사용하여 와샬(Warshall) 알고리즘으로 변형해 사용할 수 있습니다. 이는 대규모 데이터셋에서 도달 가능성 여부를 빠르게 판단하는 데 매우 효율적입니다.

# 플로이드-워셜(Floyd-Warshall) Python 구현
def floyd_warshall(v, graph):
    # graph는 인접 행렬 형태
    for k in range(1, v + 1): # 거쳐가는 노드
        for i in range(1, v + 1): # 출발 노드
            for j in range(1, v + 1): # 도착 노드
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph

[플로이드-워셜 핵심 요약]
1. 범위: 단 한 번의 실행으로 그래프 내 모든 지점 사이의 최단 거리를 산출합니다.
2. 원리: 경유지 $k$를 설정하여 기존 경로보다 빠른 우회로를 찾는 DP 방식입니다.
3. 복잡도: $O(V^3)$을 가지므로 노드 수가 적은 네트워크망의 전수 조사에 최적화되어 있습니다.