728x90
플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘임
| 기능 | 특징 | 시간복잡도 (노드 수:V) |
| 모든 노드 간에 최단 경로 탐색 | 음수 가중치가 있어도 수행 가능 DP의 원리를 이용해 알고리즘에 접근 |
O(V³) |
핵심 이론
플로이드 워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정.
최단 경로 위에 k노드가 존재한다면, 그것을 이루는 부분 경로 역시 최단 경로라는 것.
색칠된 경로가 1→5의 최단 경로라면, 1→4 최단 경로와 4→5 최단 경로 역시 색칠된 경로로 이루어질 수 밖에 없음
즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이루어진다는 의미이므로
다음과 같은 점화식을 도출 가능 함.
📌 도출한 플로이드 워셜 점화식
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
구현 방법
1. 배열 선언 및 초기화
- D[S][E] 는 노드 S에서 E까지의 최단 거리를 저장한 배열이라고 정의
- S와 E의 값이 같은 칸은
0, 다른 칸은INF로 초기화. S==E는 자기 자신에게 가는 데 걸리는 최단경로 값을 의미하기 때문
2. 최단 거리 배열에 그래프 데이터 저장
- 출발 노드는 S
- 도착 노드는 E
- 간선의 가중치는 W
- D[S][E] = W로 간선의 정보를 배열에 입력
👉 플로이드 워셜 알고리즘은 그래프를 인접 행렬로 표현함을 알 수 있음
3. 점화식으로 배열 갱신
기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 배열의 값을 갱신함
// 플로이드 워셜 알고리즘
for 경유지 K에 관해 (1~N)
for 출발 노드 S에 관해 (1~N)
for 도착 노드 E에 관해 (1~N)
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
완성된 배열은 모든 노드 간의 최단 거리를 알려줌
예를 들어1→5의 최단 거리는D[1][5] = 6으로 나타남
플로이드 워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해주므로 시간 복잡도가 빠르지 않음
해당 알고리즘을 사용해야 하는 문제는 일반적으로 노드의 개수 범위가 다른 그래프에 적게 나타남
728x90