edited by
24,125 views
34 votes
34 votes

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)$
edited by

4 Answers

Best answer
62 votes
62 votes
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$
edited by
17 votes
17 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.)

0 votes
0 votes
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is capable of handling graphs in which some of the edge weights are negative numbers.
Bellman–Ford runs in O(|V| * |E|) time, where |V| and |E| are the number of vertices and edges respectively.
Note: For complete graph: |E| = n(n-1)/2 = O(n2)
Answer:

Related questions

42 votes
42 votes
5 answers
1
Arjun asked Sep 24, 2014
29,235 views
Consider the following function:int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); }The return value of the functio...
113 votes
113 votes
8 answers
2
Arjun asked Sep 24, 2014
27,872 views
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is$\Theta(1)$$\Theta(\sqrt{\log} n)$$\Theta(\frac{\log n}{\log \log n})$$\Theta(\log n)...