노드의 모든 쌍의 최적경로를 탐색하는 알고리즘으로,
시작노드-중간노드-종점 노드의 3중 반복문을 돌려,
기존의 시작노드-종점노드까지의 거리와, 시작노드-중간노드까지의 거리 + 중간노드-종점노드까지의 거리 로
최단거리를 탐색.
3중 반복문을 사용하므로, 시간복잡도가 O(V^3)으로 굉장히 높아, 비교적 적은 수의 노드의 최적경로를 완전탐색할때 사용한다.
'CS지식 > 알고리즘 & 자료구조' 카테고리의 다른 글
| 비트마스킹 (with ChatGPT) (0) | 2024.05.05 |
|---|---|
| 다익스트라 알고리즘. (0) | 2024.03.02 |