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)$.