HomeData Modelling & AIAlgorithms | Graph Shortest Paths | Question 7

Algorithms | Graph Shortest Paths | Question 7

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!
RELATED ARTICLES

2 COMMENTS

Most Popular

Dominic
32742 POSTS0 COMMENTS
Milvus
131 POSTS0 COMMENTS
Nango Kala
7129 POSTS0 COMMENTS
Nicole Veronica
12258 POSTS0 COMMENTS
Nokonwaba Nkukhwana
12341 POSTS0 COMMENTS
Shaida Kate Naidoo
7240 POSTS0 COMMENTS
Ted Musemwa
7501 POSTS0 COMMENTS
Thapelo Manthata
7219 POSTS0 COMMENTS
Umr Jansen
7189 POSTS0 COMMENTS