Algorithms | Graph Shortest Paths | Question 7

24 June 2025

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

(A) $\Theta(n^2)$
(B) $\Theta(n^2 Logn)$
(C) $\Theta(n^3)$
(D) $\Theta(n^3 Logn)$

Answer: (C)
Explanation: Time complexity of Bellman-Ford algorithm is $\Theta(VE)$ where V is number of vertices and E is number edges (See this). If the graph is complete, the value of E becomes $\Theta(V^2)$ . So overall time complexity becomes $\Theta(V^3)$
Quiz of this Question

Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!