I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will be appreciated.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Dijkstra's algorithm visits every node once ($=O(V)$), and tries to relax all adjecent nodes via the edges. Therefore it iterates over each edge exactly twice ($=O(E)$), each time accessing the priority queue up to two times in $O(\log V)$.
Therefore the complexity is $O(E \log V + V)$.
For a proof of the correctness, just look it up at any basic algorithms book, like CLRS.
