+20 votes
3.4k views

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

1. $\theta(n^2)$
2. $\theta(n^2\log n)$
3. $\theta(n^3)$
4. $\theta(n^3\log n)$
asked
edited | 3.4k views

## 3 Answers

+39 votes
Best answer
Time complexity of Bellman-Ford algorithm is $\Theta(|V||E|)$ where $|V|$ is number of vertices and $|E|$ is number of edges. If the graph is complete, the value of $|E|$ becomes $\Theta\left(|V|^2\right)$. So overall time complexity becomes $\Theta\left(|V|^3\right)$. And given here is $n$ vertices. So, the answer ends up to be $\Theta\left(n^3\right)$.

Correct Answer: $C$
answered by Boss (19.9k points)
edited
0
Absolutely correct !

And if it for finding All pairs shortest path for every vertex, then it will be

(n*e)*n = $n^{4}$
+13 votes

as we know time complexity of bellman-ford is O(En) where E is no of edges and n is no of vertices

and in complete graph no of edges is E=n(n-1)/2  where n is no of vertices

here E=O(n2

so time complexity of bellman-ford algorithm on complete graph with n vertices is O(n3)

so ans is C.)

answered by Active (2.4k points)
0 votes

option c is correct.

1. answered by Boss (33.6k points)
Answer:

+23 votes
3 answers
1
+50 votes
5 answers
2
+37 votes
5 answers
3
+27 votes
3 answers
7