GATE Papers >> CSE >> 2013 >> Question No 19

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

• (A)  $\mathrm{\Theta }\left(n^2\right)$   
• (B)  $\mathrm{\Theta }\left(n^2\log n\right)$   
• (C)  $\mathrm{\Theta }\left(n^3\right)$   
• (D)  $\mathrm{\Theta }\left(n^3\log n\right)$