Running Time

Just like Prim's:

• Priority queue contains |V| entries, so queue operations take $O(\log\vert V\vert)$.
• Call RELAX at most once per edge, each might require an adjustment to the priority queue: $O(\vert E\vert \log \vert V\vert)$.
• Call EXTRACT-MIN once per vertex: $O(\vert V\vert\log \vert V\vert)$.
• Total: $O(\vert E\vert \log \vert V\vert)$, assuming all edges reachable from source.
• Can also implement the priority queue with a simple array and get O(|V|²) (better for dense graphs).