Question

What is the time complexity of the Bellman-Ford single-source shortest path algorithm on a completely connected weighted graph of $n$ vertices?

• A. $O(n^2)$
• B. $O(n^2 \log n)$
• C. $O(n^3)$
• D. $O(n^3 \log n)$

Hint:

Bellman-Ford runs in $O(VE)$ time, where $V$ is the number of vertices and $E$ is the number of edges.

Answer 1

The Correct Option is C

Step 1: Understanding Bellman-Ford algorithm.
The Bellman-Ford algorithm computes the shortest paths from a single source to all other vertices by repeatedly relaxing all edges in the graph.
Step 2: Determining the number of edges.
In a completely connected (complete) graph with $n$ vertices, the number of edges is: \[ E = n(n-1) \approx O(n^2) \]
Step 3: Analyzing the number of iterations.
The Bellman-Ford algorithm relaxes all edges exactly $(n-1)$ times.
Step 4: Computing total time complexity.
\[ \text{Time} = (n-1) \times O(n^2) = O(n^3) \]
Step 5: Final conclusion.
Hence, the time complexity of the Bellman-Ford algorithm on a complete graph is $O(n^3)$.

Answer 2

Bellman-Ford relaxes every edge in the graph, and it repeats this relaxation pass \(n-1\) times to guarantee the shortest paths have propagated across the whole graph. On a complete graph, every vertex connects to every other vertex, so we have \(O(n^2)\) edges. Let's check each option against "number of passes times work per pass":

1. \(O(n^2)\): This would be the cost of relaxing all edges just once. But Bellman-Ford needs \(n-1\) full passes over the edge list to guarantee convergence, not a single pass, so this undercounts the work by a factor of \(n\).
2. \(O(n^2 \log n)\): The extra \(\log n\) factor would apply if some priority-queue or sorting step were involved per pass, as in Dijkstra's implementation with a heap. Bellman-Ford does no such sorting, it just linearly scans the edge list each pass, so there's no \(\log n\) term.
3. \(O(n^3)\): Each of the \(n-1\) passes relaxes all \(O(n^2)\) edges, giving total work \((n-1) \times O(n^2) = O(n^3)\). This matches exactly how the algorithm is structured, with no unaccounted factor.
4. \(O(n^3 \log n)\): Like option B, this tacks on a logarithmic factor that has no source in Bellman-Ford's straightforward edge-relaxation loop.

Only multiplying the \(n-1\) passes by the \(O(n^2)\) edges per pass, with no extra logarithmic term, matches how the algorithm actually runs.

Therefore, the correct answer is \(O(n^3)\).