Dijkstra’s shortest path algorithm is O(ElogV)
where:
V
is the number of verticesE
is the total number of edges
Your analysis is correct, but your symbols have different meanings! You say the algorithm is O(VElogV)
where:
V
is the number of verticesE
is the maximum number of edges attached to a single node.
Let’s rename your E
to N
. So one analysis says O(ElogV)
and another says O(VNlogV)
. Both are correct and in fact E = O(VN)
. The difference is that ElogV
is a tighter estimation.