[알고리즘] 플로이드-워셜 알고리즘

설명  그래프 내에 존재하는 두 정점 사이의 최단 경로를 찾는 알고리즘. 모든 정점 쌍에 대한 최단 경로를 계산할 수 있다. 만약 정점의 개수가 n일 경우 n * n크기의 2차원 배열을 생성한 뒤, 각 정점 사이의 거리를 초기화해준다. 이후 그래프 내 모든 정점을 중간 정점으로 사용하여 가능한 경로를 탐색해 나간다. 만약 a에서 b로 가는 경로를 구할 때, 중간 정점을 c라 한다면 a -> c에서 c->b로 가는 경로의 거리와 비교해 최단 거리를 갱신한다. 이 과정을 반복하여 모든 정점 사이의 최단거리를 구한다.  시간 복잡도: O(n3) 알고리즘 문제에서는 보통 정점의 개수가 약 100 ~ 1000개 정도로 나온다. 예시  아래와 같은 그래프의 최단 경로를 구할 경우 먼저 거리의 배열을 초기화 한다. ..
알고리즘/알고리즘 이론 2024. 8. 28. 12:09
1