플로이드-워셜
- 플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
| 기능 |
특징 |
시간 복잡도(노드 수: V) |
| 모든 노드 간에 최단 경로 탐색 |
- 음수 가중치 에지가 있어도 수행할 수 있음 - 동적 계획법의 원리를 이용해 알고리즘에 접근 |
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, 다른 칸은 ∞로 초기화 한다. 여기에서 S == E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문이다.
➡️ 2단계: 최단 거리 배열에 그래프 데이터 저장하기
- 출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 배열에 입력한다. 이로써 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.