Time and Space Complexity
Coddy의 다익스트라 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 7번째.
시간 복잡도:
- 여기에 작성된 대로 O(V2 + V*E)입니다 (V번의 각 라운드에서 정점을 스캔하여 최솟값을 찾고 간선을 스캔하여 완화(relax)합니다). 이진 힙(binary heap)과 인접 리스트(adjacency list)를 사용하면 O((V + E) log V)로 개선됩니다.
공간 복잡도:
- 거리(distance) 및 방문(visited) 배열을 위한 O(V) (입력 간선 포함).
요약:
- 다익스트라(Dijkstra)는 가장 가까운 정점을 탐욕적으로 확정하고 그 간선들을 완화(relax)함으로써, 음수가 아닌 가중치에 대한 단일 출발점 최단 거리를 찾습니다.
- 음수 간선이 있는 경우에는 작동하지 않습니다. 그런 경우에는 벨만-포드(Bellman-Ford) 알고리즘을 사용하세요.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
다익스트라 알고리즘 - 그래프 알고리즘의 모든 레슨
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity