GATE CS 2013 Q19 — Shortest Paths (Dijkstra, Bellman-Ford)

The Bellman-Ford algorithm is used to find the single-source shortest paths in a weighted graph. Its standard time complexity is given by:

$$\text{Time Complexity} = \Theta(V \cdot E)$$

where:

• $V$ is the number of vertices.
• $E$ is the number of edges.

For a complete graph with $n$ vertices:

• The number of vertices is $V = n$.
• The number of edges in a complete graph is $E = \frac{n(n-1)}{2}$ (for undirected) or $E = n(n-1)$ (for directed). In both cases, the number of edges is $E = \Theta(n^2)$.

Substituting these values into the complexity formula:

$$\text{Time Complexity} = \Theta(n \cdot n^2) = \Theta(n^3)$$

Hence, the correct option is C.