728x90
반응형
이론
이번에 볼 알고리즘은 플로이드-워셜이다. 플로이드 워셜은 다익스트라 알고리즘이랑 비슷한점은 a → b 최단 거리를 구하는 것인데 다익스트라는 시작점과 끝점이 있다는것고 플로이드 워셜은 각 노드간의 최단 거리를 구하는 것이다.
하지만 다익스트라와 다르게 구현이 간단하는데 시간복잡도는 O(N^3)이라는 긴 시간 복잡도를 간진다.
자세한 설명은 아래의 사이트에서 확인 해봐라
플로이드-워셜 알고리즘 - 나무위키
이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외) 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권
namu.wiki
728x90
반응형
'알고리즘 > 이론' 카테고리의 다른 글
| [알고리즘 이론] 최단경로 알고리즘(다익스트라) (0) | 2022.12.23 |
|---|---|
| [알고리즘 이론] 그래프(Grape) (0) | 2022.12.23 |
| [알고리즘 이론] 넓이 우선 탐색(BFS) (0) | 2022.12.20 |
| [알고리즘 이론] 깊이 우선 탐색(DFS) (0) | 2022.12.19 |
| [알고리즘 이론] 동적계획법(Dynamic Programming, DP) (0) | 2022.12.14 |