📌 강의 자료
Google Colaboratory
📌 강의 내용
플로이드-와샬 알고리즘
- 그래프 이론에서 모든 정점 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치를 포함한 가중치가 있는 그래프에서도 사용할 수 있습니다. 주로 "모든 쌍 최단 경로" 문제를 해결하는데 사용됩니다.
- 플로이드-와샬 알고리즘은 다음과 같은 기본 아이디어로 작동합니다
- 모든 정점 쌍 (u, v)에 대한 최단 경로를 초기화합니다. 초기에는 직접 연결된 간선의 가중치로 설정하거나 연결이 없는 경우 무한대(또는 충분히 큰 값)로 설정합니다.
- 모든 중간 정점을 순차적으로 선택하면서, 현재 선택한 중간 정점을 경유해서 두 정점 (u, v) 간의 최단 경로를 검사하고 갱신합니다. 즉, 각 정점 쌍 (u, v)에 대해 모든 정점 k를 중간 경로로 고려하여 경로 최단화를 시도합니다. 이 과정을 반복하여 모든 최단 경로를 찾습니다.
- 위 과정을 모든 정점 쌍에 대해 반복하면, 최종적으로 모든 정점 쌍 간의 최단 경로를 구할 수 있습니다.
- 플로이드-와샬 알고리즘은 다음과 같은 특징을 가집니다:
- 음수 가중치를 포함한 가중치가 있는 그래프에서도 동작합니다.
- 모든 정점 쌍 간의 최단 경로를 한 번에 계산할 수 있어서, "모든 쌍 최단 경로" 문제를 효과적으로 해결할 수 있습니다.
- 시간 복잡도는 O(V^3)입니다. 여기서 V는 정점의 수입니다.
- 플로이드-와샬 알고리즘은 주로 그래프의 구조를 변화시키지 않고 최단 경로를 계산할 때 사용되며, 예를 들어 네트워크 라우팅, 지도 애플리케이션에서 최단 경로 찾기, 게임에서 최단 경로 찾기 등 다양한 응용 분야에서 활용됩니다.
📌 문제 풀이