그래프 이론에서 가장 중요한 문제 중 하나는 최단 경로 찾기입니다. 플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프의 모든 정점 쌍 사이의 최단 경로를 한 번에 계산할 수 있는 강력한 알고리즘입니다. 특히 음수 가중치 간선이 있지만 음수 사이클이 없는 그래프에서도 사용할 수 있다는 장점이 있습니다.
작동 원리와 구현
플로이드-워셜 알고리즘은 동적 프로그래밍 접근법을 사용하여 점진적으로 최단 경로를 개선해 나갑니다. 핵심 아이디어는 중간 정점을 경유하는 경로가 기존의 직접 경로보다 짧은지 확인하고, 더 짧다면 이를 업데이트하는 것입니다.
알고리즘은 3중 반복문 구조를 가지며, 외부 루프는 중간 정점 k를 순회합니다. 두 정점 i와 j 사이의 최단 경로는 정점 k를 경유하는 경로(i→k→j)와 직접 연결된 경로(i→j) 중 더 짧은 것으로 결정됩니다.
플로이드-워셜 알고리즘의 시간 복잡도는 O(V³)로, 정점의 수가 많은 대규모 그래프보다는 정점 수가 적은 밀집 그래프에서 효율적입니다.
구현 과정에서 주의할 점은 초기 그래프 설정입니다. 자기 자신으로의 거리는 0으로, 직접 연결되지 않은 정점 간의 거리는 무한대로 설정해야 합니다. 알고리즘 실행 후, dist[i][j]는 정점 i에서 j까지의 최단 거리를 나타냅니다. 최종 그래프가 행렬이기 때문에 그래프를 구현할 때 보통 인접 행렬로 구현합니다.
다음은 파이썬으로 구현한 간단한 플로이드-워셜 알고리즘입니다:
증명과 쓰임
플로이드-워셜 알고리즘의 증명
플로이드-워셜 알고리즘의 정확성은 동적 프로그래밍의 최적 부분 구조 속성을 통해 증명할 수 있습니다. 알고리즘의 핵심은 다음 귀납적 정의에 있습니다:
dist[i][j]^k는 0부터 k까지의 정점만을 중간 정점으로 사용하여 i에서 j까지 가는 최단 경로의 길이입니다. 이때:
- k = -1인 경우: 중간 정점을 사용하지 않음을 의미하므로, dist[i][j]^(-1)은 i에서 j로 직접 연결된 간선의 가중치입니다.
- k ≥ 0인 경우: dist[i][j]^k = min(dist[i][j]^(k-1), dist[i][k]^(k-1) + dist[k][j]^(k-1))
이 관계식은 k번째 정점을 경유 정점으로 포함하는 경우와 포함하지 않는 경우 중 더 짧은 경로를 선택한다는 것을 의미합니다. 모든 k(0에서 V-1까지)에 대해 이 과정을 반복하면, 최종적으로 모든 정점 쌍 사이의 최단 경로를 구할 수 있습니다.
플로이드-워셜 알고리즘의 코딩테스트 활용
플로이드-워셜 알고리즘은 코딩 테스트에서 자주 등장하는 알고리즘으로, 다음과 같은 문제 유형에 적용됩니다:
- 경로 존재 여부 확인: 두 정점 사이에 경로가 있는지 확인하는 문제에서 플로이드-워셜을 통해 모든 정점 쌍의 연결성을 파악할 수 있습니다.
- 최소 비용 문제: 여러 도시를 방문해야 할 때 각 도시 간 이동 비용의 최솟값을 구하는 문제에 활용됩니다.
- 우회 경로 문제: 특정 정점이나 간선을 거쳐야 하거나 피해야 하는 제약이 있는 최단 경로 문제에서 활용됩니다.
- 순위 결정 문제: 게임이나 대회의 결과가 일부만 주어질 때, 전체 순위를 결정할 수 있는지 확인하는 문제에 응용됩니다.
- 사이클 탐지: 특정 조건을 만족하는 사이클의 존재 여부를 확인하는 문제에서 변형하여 사용됩니다.
- 경로 복원: 최단 경로의 실제 경로(정점 순서)를 추적해야 하는 문제에서 별도의 경로 저장 배열과 함께 활용됩니다.
코딩 테스트에서 플로이드-워셜 알고리즘이 유리한 점은 구현이 매우 직관적이고 간결하다는 것입니다. 단 3중 반복문으로 모든 정점 쌍의 최단 거리를 계산할 수 있어, 다익스트라나 벨만-포드 알고리즘보다 구현 난이도가 낮습니다. 다만 O(V³) 시간 복잡도로 인해 정점 수가 많은 문제(일반적으로 500개 이상)에서는 시간 초과가 발생할 수 있으므로 문제의 제약 조건을 잘 확인해야 합니다.
다익스트라와의 차이점
플로이드-워셜 알고리즘과 다익스트라 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘이지만, 접근 방식과 용도에서 중요한 차이점이 있습니다:
1. 기본 개념의 차이
- 다익스트라 알고리즘: 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 그리디 알고리즘 방식을 사용하여 현재까지 발견된 가장 짧은 경로를 선택해 탐색을 진행합니다.
- 플로이드-워셜 알고리즘: 모든 정점 쌍 사이의 최단 경로를 한 번에 계산하는 알고리즘으로, 다이나믹 프로그래밍 방식을 사용합니다.
2. 시간 복잡도 비교
- 다익스트라 알고리즘: 우선순위 큐를 사용할 경우 O(E log V), 여기서 E는 간선의 수, V는 정점의 수입니다.
- 플로이드-워셜 알고리즘: O(V³) 시간 복잡도를 가지므로, 정점 수가 많은 그래프에서는 다익스트라보다 비효율적입니다.
3. 음수 가중치 처리
- 다익스트라 알고리즘: 음수 가중치 간선이 있는 그래프에서는 정확한 결과를 보장하지 않습니다.
- 플로이드-워셜 알고리즘: 음수 가중치 간선이 있어도 올바른 결과를 계산할 수 있으며, 음수 사이클 검출도 가능합니다.
4. 구현 복잡성
- 다익스트라 알고리즘: 우선순위 큐 등의 자료구조를 활용해야 하므로 구현이 비교적 복잡합니다.
- 플로이드-워셜 알고리즘: 3중 반복문만으로 구현이 가능하여 매우 직관적이고 간결합니다.
5. 활용 상황에 따른 선택
- 다익스트라를 선택해야 할 때: 특정 출발점에서의 최단 경로만 필요하거나, 정점 수가 많은 희소 그래프에서 효율성이 중요할 때
- 플로이드-워셜을 선택해야 할 때: 모든 정점 쌍의 최단 경로가 필요하거나, 음수 가중치가 있거나, 정점 수가 적은 밀집 그래프에서 사용
플로이드-워셜 알고리즘은 간결한 구현과 높은 적용성으로 그래프 관련 알고리즘 문제 해결에 강력한 도구가 됩니다. 특히 모든 정점 쌍의 최단 거리를 한 번에 계산해야 하는 문제나 음수 가중치가 있는 경우에 유용하며, 코딩 테스트에서도 정점 수가 제한적인 다양한 문제에 효과적으로 적용할 수 있습니다. 동적 프로그래밍의 아름다움을 보여주는 이 알고리즘의 원리를 이해하고 적절한 상황에 활용한다면, 복잡한 그래프 문제도 우아하게 해결할 수 있을 것입니다.