| 대상 : st -> ed (지정 | 시간 복잡도 | 비고 | |
| Unweighted | BFS | O( V+E) | |
| weighted (positive) | Dijkstra | (PQ) - O(ElogV) | 아직 선택 되지 않은 vertex중 최단 거리에 도달 할 수 있는 노드 선택, 해당 노드에서 나가는 edge 중를 기반으로, 업데이트 할 노드가 있다면 업데이트 Edge relaxation dist(a)=min(dist(a)+dist(cur)+edge(cur,a)) |
| weighted (negative) - negative cycle 탐지 |
Bellman-Ford Algorithm | O(E*V) | Edge Relaxation을 V-1회 적용 (도달 최소 거리) 만약 V번째 (한번더) 수행시 업데이트 되는 구간이 있다면, negative cycle 존재 |
| 대상 : 모든 v -> 모든 v | |||
| Floyd-Warshall Algorithm | O( V^3) | node k가 st -> ed 까지 도달하는 최단 경로에 존재할지 안할지를 모든 쌍에 대해서 확인 + 모든 k에 대해서 확인 하면 최단 경로 참조 수식은 아래 참고 |
'Computer Science > DataScience' 카테고리의 다른 글
| New Feature Research For Data Analysis (0) | 2020.11.25 |
|---|