GATE CS Mastery
Cheat sheets

GATE CS 2013 · Algorithms

Question 19

MCQPrinted as CS Q.191 markWrong answer: −1/3Easy (estimate)

Question

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

Choose one option
Official answer and solution
Official answer
C
From
Official GATE 2013 answer key

Solution

Substitute the vertex and edge counts of a complete graph Kn into the Bellman-Ford time complexity formula.

The Bellman-Ford algorithm finds single-source shortest paths in an arbitrary weighted directed graph G=(V,E)G = (V, E):

  • It performs ∣V∣−1|V| - 1 passes of edge relaxation.
  • In each pass, it relaxes all ∣E∣|E| edges.
  • Total running time is Θ(∣V∣⋅∣E∣)\Theta(|V| \cdot |E|).

For a complete graph on nn vertices:

  • Number of vertices ∣V∣=n|V| = n.
  • Number of edges ∣E∣=(n2)=n(n−1)2=Θ(n2)|E| = \binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^2).

Substituting into the complexity formula:

Time Complexity=Θ(∣V∣⋅∣E∣)=Θ(n⋅n2)=Θ(n3)\text{Time Complexity} = \Theta(|V| \cdot |E|) = \Theta(n \cdot n^2) = \Theta(n^3)

This matches option C.

Final answer

Option (C)

Common trap

Using the edge count of a sparse graph (∣E∣=Θ(n)|E| = \Theta(n)) rather than a complete graph (∣E∣=Θ(n2)|E| = \Theta(n^2)).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2013 Computer Science and Information Technology (CS)
Question
19 of 65, printed as CS Q.19
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.