GATE 2013 CS (CS1) – Question 29

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

What is Bellman–Ford’s running time on a complete graph with n vertices?

$\Theta(n^2)$
$\Theta(n^2\log n)$
$\Theta(n^3)$
$\Theta(n^3\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(n^3)$

Explanation

The standard algorithm relaxes all edges over n−1 passes, costing Θ(VE). A complete graph has Θ(n²) edges, so this becomes Θ(n·n²)=Θ(n³), C, for the standard full-pass worst-case bound.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2011 CS (CS1) Q64 – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2;…
GATE 2011 CS (CS1) Q65 – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2;…
GATE 2010 CS (CS1) Q60 – The undirected graph on vertices 0,…,4 has weight matrix…
GATE 2010 CS (CS1) Q61 – The undirected graph on vertices 0,…,4 has weight matrix…
GATE 2015 CS (CS2) Q47 – Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3…
GATE 2015 CS (CS3) Q55 – A connected undirected graph has 100 vertices and 300 edges. Its minimum spanning-tree…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →