< Floyd Warshall >
한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
시간복잡도 On^3)
1. 시작점이 주어지고, 가중치가 양수일 때
=> 다익스트라 알고리즘 O(n^2) / O(nlogN)
2. 시작점이 주어지지만, 가중치가 음수일 때
BellmanFord 알고리즘 O(n^2)
3. 시작점이 주어지지 않고, 가중치가 음수일 때
Floyd Warshall O(n^2)
▷ 기본 개념설명
'Game AI & Unity > concepts' 카테고리의 다른 글
| [Dijkstra(improved ver)] 경유지를 뽑을 때, 우선순위 큐 사용 (0) | 2024.03.04 |
|---|---|
| [우선순위 큐 (Priority Queue)] (0) | 2024.03.04 |
| [Union Find] 무방향 그래프에서 사이클 발생 유무 확인하기 (0) | 2024.02.26 |
| [최소 신장 트리 MST(Minimum Spanning Tree)] 최소 비용으로 정점 연결시키기 (0) | 2024.02.23 |
| [Two Pointer] 탐색구간이 정해져있지 않을 때, 구간 합 구하기 (0) | 2024.02.23 |