The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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)$
asked in Algorithms by Veteran (346k points)
edited by | 2.4k views

2 Answers

+34 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 answers ends up to $\Theta\left(n^3\right)$.
answered by Veteran (19.8k points)
+9 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 Veteran (10k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
38,389 users