다익스트라 알고리즘 시간복잡도에 대해서... ElogE? ElogV?

이해가 잘 안되서 질문드립니다.

보통 다익스트라 알고리즘의 시간복잡도가 V^2, ElogV 이렇게 두 가지가 있는 걸로 알고있습니다.(피보나치 힙 E+VlogV 제외)

V^2 의 경우는 모든 정점에 대해서(V) 최소 거리(배열의 최소값)를 찾는(V)작업을 하기 때문에 V^2 인걸 알겠는데요..(경우에 따라선 기존 거리와 새로운 거리의 비교횟수인 E를 더해주기도 합니다만..)

ElogV의 경우(힙)에는 구글링해서 살펴보면 원래 ElogE인데, 중복간선이 없는 그래프의 경우에는 E는 보통 V^2를 넘지 않으니까 ElogV^2 = 2ElogV = O(ElogV) 가 된다고 설명을 하더군요. 나무위키?랑 다른 블로그를 봐도 이렇게 나와있습니다.

여기서 제가 궁금한게

다익스트라 알고리즘이 distance[V]라는 배열을 계속 업데이트하면서 미니멈을 pop하는 형식이잖아요?

그럼 애초에 힙을 V개만 유지할텐데, 어떻게해서 ElogE라는 식이 나오는지 모르겠습니다. 그냥 바로 ElogV가 나오는거같은데..

애초에 엣지의 수 만한 배열이 필요가 없지않나요? V크기의 힙을 한번 업데이트하는데 logV가 소요되고, 이걸 각 정점의 모든 간선에 대해 한번 씩 진행하니까 E를 곱해주는거같은데..

아 물론 여기서도 기존의 distance와 새로 구해진 distance의 비교는 E번만큼 이루어지니까 E를 더해주어야 하지만, E + ElogV에서 빅오표기법을 하면 E는 사라지니까 제외하였씁니다.

질문이 좀 길었는데 감사합니다.