Time and Space Complexity
Lesson 7 of 9 in Coddy's Dijkstra's Algorithm - Graph Algorithms course.
Time Complexity:
- O(V2 + V*E) as written here (each of the V rounds scans vertices to find the minimum and scans the edges to relax). With a binary heap and an adjacency list it improves to O((V + E) log V).
Space Complexity:
- O(V) for the distance and visited arrays (plus the input edges).
Summary:
- Dijkstra finds single-source shortest distances for non-negative weights by greedily finalizing the closest vertex and relaxing its edges.
- It does not work with negative edges; use Bellman-Ford for those.
Try it yourself
This lesson doesn't include a code challenge.
Test yourselfThis lesson includes a short quiz. Start the lesson to answer it and track your progress.
All lessons in Dijkstra's Algorithm - Graph Algorithms
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity