Course contentsShow
← Computer Science
Lesson 986 of 2,87223. Shortest Path AlgorithmsFree lesson

Bellman-Ford Time Complexity

Analyzing the O(VE) time complexity and understanding why it's slower than Dijkstra's.

Bellman-Ford Time Complexity

What you'll learn: You'll understand why Bellman-Ford runs in O(VE) time and why it's slower than Dijkstra's algorithm.


Breaking Down the O(VE) Complexity

The Bellman-Ford algorithm relaxes every edge in the graph exactly V-1 times (where V is the number of vertices). This is the heart of its time complexity.

  • Outer loop: Runs V-1 times (one iteration per possible edge in the shortest path)
  • Inner loop: Examines all E edges (where E is the total number of edges)
  • Total operations: (V-1) × E ≈ O(VE)

Each relaxation operation itself is O(1), but you're doing it V×E times total.

Why So Much Slower Than Dijkstra's?

Dijkstra's algorithm with a binary heap runs in O((V + E) log V). On sparse graphs where E ≈ V, this can be much faster than O(VE).

The key difference: Dijkstra's intelligently selects which vertex to process next (the closest unvisited one), avoiding redundant work. Bellman-Ford, by contrast, blindly relaxes all edges repeatedly, doing the same work over and over until the distances stabilize.

Think of it like this: Dijkstra's is like following the shortest routes on a map systematically. Bellman-Ford is like trying every possible route V-1 times until you're sure you've found the shortest ones.

The Tradeoff

Bellman-Ford's brute-force approach makes it slower, but it gains the ability to handle negative edge weights and detect negative cycles—something Dijkstra's cannot do.

Key Takeaway: Bellman-Ford's O(VE) time complexity comes from relaxing all E edges V-1 times, making it significantly slower than Dijkstra's O((V+E) log V), but this exhaustive approach enables handling negative weights.