다익스트라일반시간복잡도1 다익스트라 알고리즘 Dijkstra's algorithm 일정 시간 복잡도 다익스트라 알고리즘은 시작 정점이 정해져있다. 정점을 선택해가며 진행하고 각 정점까지 총 가중치를 합한 값을 저장하고 비교해 나간다. 앞서 살펴본 프림 알고리즘의 일정 시간 복잡도와 유사하다. T(n) = 2(n-1)(n-1)로 모든 정점을 방문하기 위해서는 시작 정점을 제외하고 n-1개의 정점을 방문해야한다. 그러므로 repeat n-1번을 해준다 (가장 바깥쪽 반복문) 이 repeat내부에서는 각 정점까지 현재 진행상태에서의 최단거리를 비교하고 (n-1번) 이동할 정점을 고른 후에는 다시 각 정점까지의 거리를 업데이트한다 (n-1번) 그렇기 때문에 (n-1 + n-1)(n-1) = 2(n-1)(n-1)이 되는 것이다. 의사 코드를 보면 다음과 같다. void dijkstra(int n, const n.. 2021. 6. 9. 이전 1 다음