플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
쉽게 풀면
여러 도시 사이의 거리표를 만든다고 해봅시다. "서울에서 부산까지"뿐 아니라 "모든 도시에서 모든 도시까지"의 최단 거리를 한꺼번에 알고 싶을 때가 있습니다. 플로이드-워셜 알고리즘은 "각 도시를 하나씩 경유지 후보로 넣어보면서, 그 경유지를 거쳐 가는 게 더 빠른지 확인한다"는 아이디어를 모든 도시에 대해 차례로 반복합니다. 정점이 N개면 이 과정을 N번 반복하면서 거리표 전체를 조금씩 갱신해, 마지막에는 모든 정점 쌍의 최단 거리가 완성됩니다. 코드가 간단한 삼중 반복문으로 짜인다는 것도 특징입니다.
왜 중요한가
많은 네트워크 분석 문제는 결국 "모든 지점 쌍 사이의 관계"를 알아야 풀립니다. 교통망 최적화, 통신 라우팅, 소셜 네트워크의 근접 중심성 계산처럼 전역적인 거리 정보가 필요한 연구에서는 한 번의 계산으로 전체 거리 행렬을 얻을 수 있는 플로이드-워셜 알고리즘이 표준적인 도구로 쓰입니다. 또한 구현이 단순해 다른 그래프 알고리즘의 비교 기준(baseline)으로도 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 "네트워크 안의 모든 지점 조합에 대한 최단 거리를 한 번의 계산으로 모두 구했다"는 뜻입니다. 교통망 분석, 라우팅 테이블 계산, 소셜 네트워크 거리 분석 등에서 자주 사용됩니다.
물류·교통 최적화 연구에서는 매번 경로를 새로 계산하는 대신, 미리 구해둔 전체 거리 행렬을 다른 최적화 모형에 재사용하는 방식으로 이 알고리즘을 활용한다는 뜻입니다.
생물정보학 연구에서는 유전자나 단백질 간 상호작용을 그래프로 표현한 뒤, 이 알고리즘으로 네트워크 전체의 연결성과 구조적 특성을 정량적으로 요약할 때 사용한다는 의미입니다.
조금 더 깊게 보면
플로이드-워셜 알고리즘은 동적 계획법(dynamic programming)의 대표적인 사례로, "경유지를 하나씩 늘려가며 최적해를 갱신한다"는 점화식 구조를 가집니다. 시간 복잡도는 일반적으로 정점 수의 세제곱(O(V³))으로 알려져 있어 정점이 매우 많은 대규모 그래프에는 부담이 크며, 이 때문에 실제 논문에서는 그래프 규모에 따라 다익스트라 알고리즘을 모든 정점에 반복 적용하는 방식과 성능을 비교하기도 합니다. 또한 음수 가중치가 있는 그래프에서도 동작할 수 있다는 점이 다익스트라 알고리즘과 대비되는 특징으로 자주 언급됩니다.
주의할 점
플로이드-워셜 알고리즘은 정점 수가 많아질수록 계산량이 정점 수의 세제곱에 비례해 급격히 늘어나므로, 특정 한 지점에서 출발하는 최단 경로만 필요하다면 훨씬 가벼운 다익스트라 알고리즘을 쓰는 것이 더 효율적입니다.