Time and Space Complexity
Lesson 7 of 9 in Coddy's Bellman-Ford Algorithm - Graph Algorithms course.
Time Complexity:
- O(V * E): V-1 passes, each relaxing all E edges.
Space Complexity:
- O(V) for the distance array (plus the input edges).
Summary:
- Bellman-Ford finds single-source shortest distances even with negative edges, by relaxing every edge V-1 times.
- One extra pass detects negative cycles. It is slower than Dijkstra but more general.
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 Bellman-Ford Algorithm - Graph Algorithms
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity