Dijkstra Time Complexity (Big-O)
Dijkstra's algorithm computes single-source shortest paths on a graph with non-negative edge weights in O((V + E) log V) using a binary heap, with O(V) space.
Open the interactive DevRef Hub tool →Key facts
| Time (binary heap) | O((V + E) log V) |
|---|---|
| Space | O(V) |
| Constraint | Non-negative edge weights |
| Type | Single-source shortest path |
Frequently asked questions
What is the time complexity of Dijkstra?
O((V + E) log V) with a binary-heap priority queue.
Why must edge weights be non-negative?
Negative weights break the greedy assumption; use Bellman-Ford instead.
Related pages
Big-O of Dijkstra is part of DevRef Hub on GOAT Lab — a free reference you can use without signing up, and it works offline. Open the tool above for any custom value.
Part of GOAT Lab — 26 free, browser-based science, engineering and developer tools. No sign-up.