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

The standard Bellman-Ford algorithm runs in $\Theta(|V| \cdot |E|)$ time, where $|V|$ is the number of vertices and $|E|$ is the number of edges.

For a complete graph with $n$ vertices:

• $|V| = n$

• $|E| = \binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^2)$

Therefore, the overall time complexity is:

Hence, the correct option is (C).