What is the time complexity of Bellman-Ford single-source shortest path…
20132013
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of \(n\) vertices?
- A.
\(Θ(n^2)\) - B.
\( Θ(n^2 \ log \ n) \) - C.
\(Θ(n^3)\) - D.
\( Θ(n^3 \ log \ n) \)
Attempted by 293 students.
Show answer & explanation
Correct answer: C
Key idea: Bellman-Ford performs |V|-1 iterations and relaxes every edge in each iteration, so its running time is Θ(V·E).
Step 1: General running time is Θ(V·E) (V = number of vertices, E = number of edges).
Step 2: For a complete graph with n vertices, E = n(n−1)/2 = Θ(n^2).
Step 3: Substitute E = Θ(n^2) and V = n into Θ(V·E) to get Θ(n·n^2) = Θ(n^3).
Therefore, the time complexity of Bellman-Ford on a complete graph of n vertices is Θ(n^3).
A video solution is available for this question — log in and enroll to watch it.