Dijsktra 알고리즘의 최소값 버텍스를 고려하는 방법은 무엇입니까?

Question

나는이 게시물 Understanding Time complexity calculation for Dijkstra Algorithm을 읽고 Dijkstra 알고리즘의 복잡성을 이해했습니다. 그러나 각 반복에서 힙 내부의 최소값 버텍스 (값이이 반복 이후에 고정 될 값)가 계산에 포함되는 곳을 볼 수는 없습니다 ... 누군가가 나를 어디에 있는지 명확하게 설명 할 수 있습니까? 참여 했니?

감사합니다.

Answer 1

다 익스트라 알고리즘은 첫 번째 사이클은 V 반복을하고 두 번째는 모든 정점 반복의 정도의 합을 만드는이

repeat V times: 
    take min from heap; // Works in O(1) 
    erase min from heap; // Works in O(log V) 
    for vertices connected with current: 
     update distance; // Works in O(1) 
     update value in heap; // Works in O(log V) 

같은 것입니다, 그래서 2 * E 또는 O(E) 반복합니다. 총 복잡도는 O(VlogV + ElogV)

입니다.