플로이드 워샬 알고리즘이란?

플로이드-워샬 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 동적 계획법(Dynamic Programming)을 기반으로 한다.

알고리즘의 주요 핵심은 "거쳐가는 정점"을 기준으로 최단 경로를 구하는 것입니다. 즉, 모든 정점을 순서대로 거쳐가면서 해당 정점을 중간 지점으로 설정하여 최단 경로를 갱신한다.

다음은 플로이드-워샬 알고리즘의 동작 원리이다.

1. 초기 그래프 설정: 그래프의 인접 행렬을 생성하고, 각 간선의 가중치 값을 초기화한다.
2. 거쳐가는 정점 순회: 모든 정점을 순회하면서 해당 정점을 거쳐가는 경우를 고려한다.
3. 최단 경로 갱신: 현재까지 구한 최단 경로와 비교하여 더 짧은 경로가 있다면 해당 값을 업데이트한다.
4. 반복 수행: 모든 정점을 거쳤을 때까지 2번과 3번 단계를 반복한다.

앞선 과정이 완료되면, 인접 행렬에 저장된 값들은 모든 정점 쌍 간의 최단 경로 길이를 나타내게 된다.

플로이드-워샬 알고리즘은 시간 복잡도가 O(V^3) 이다. 여기서 V는 그래프의 정점 수를 의미한다.

따라서 크기가 작거나 중간 크기의 그래프에 대해서 효율적으로 동작하는 알고리즘이라 할 수 있다.

이 알고리즘은 하나의 지역에서 다른 모든 지역까지의 최단 경로를 찾아야 하는 경우에 유용하게 사용된다.

다시 풀어보기 : 프로그래머스 합승 택시 요금 level3