Question:
What is the time complexity of the Bellman-Ford single-source shortest path algorithm on a completely connected weighted graph of $n$ vertices?
What is the time complexity of the Bellman-Ford single-source shortest path algorithm on a completely connected weighted graph of $n$ vertices?
Show Hint
Bellman-Ford runs in $O(VE)$ time, where $V$ is the number of vertices and $E$ is the number of edges.
Updated On: Feb 8, 2026
- $O(n^2)$
- $O(n^2 \log n)$
- $O(n^3)$
- $O(n^3 \log n)$
Hide Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: Understanding Bellman-Ford algorithm.
The Bellman-Ford algorithm computes the shortest paths from a single source to all other vertices by repeatedly relaxing all edges in the graph.
Step 2: Determining the number of edges.
In a completely connected (complete) graph with $n$ vertices, the number of edges is: \[ E = n(n-1) \approx O(n^2) \]
Step 3: Analyzing the number of iterations.
The Bellman-Ford algorithm relaxes all edges exactly $(n-1)$ times.
Step 4: Computing total time complexity.
\[ \text{Time} = (n-1) \times O(n^2) = O(n^3) \]
Step 5: Final conclusion.
Hence, the time complexity of the Bellman-Ford algorithm on a complete graph is $O(n^3)$.
The Bellman-Ford algorithm computes the shortest paths from a single source to all other vertices by repeatedly relaxing all edges in the graph.
Step 2: Determining the number of edges.
In a completely connected (complete) graph with $n$ vertices, the number of edges is: \[ E = n(n-1) \approx O(n^2) \]
Step 3: Analyzing the number of iterations.
The Bellman-Ford algorithm relaxes all edges exactly $(n-1)$ times.
Step 4: Computing total time complexity.
\[ \text{Time} = (n-1) \times O(n^2) = O(n^3) \]
Step 5: Final conclusion.
Hence, the time complexity of the Bellman-Ford algorithm on a complete graph is $O(n^3)$.
Was this answer helpful?
0
0
Top Questions on Data Structures
- What is the value of the postfix expression: $6\ 12\ 2\ 4\ +\ /\ *\ ?$
- Consider the following C function foo(int n). How many times does foo(2) get called on making the call foo(5)?
C Function:
float foo(int n){ if(n <= 2) return 1; else return (2*foo(n-1) + 3*foo(n-2)); } - Suppose you are given pointers to the first and the last nodes of a singly linked list, which one of the following operations would require traversal of the linked list?
- Which one of the following recurrence relations best represents the time complexity of the binary search algorithm running on an ordered array of $n$ elements?
- How many null links does an arbitrary binary tree with $n$ nodes have?
View More Questions
Questions Asked in OJEE exam
Consider the grammar $S \rightarrow aSa \mid bSb \mid a \mid b$. Which one of the following options correctly characterizes the language generated by the given grammar over the alphabet {a,b}
- OJEE - 2025
- Theory of Computations
If a concentrated load of 50 kN is applied at point C, then what will be the shear developed at point C?
- OJEE - 2025
- Strength of Materials
- To generate the $j^{\text{th}}$ column of the flexibility matrix
- OJEE - 2025
- Structural Analysis
- According to the penetration theory of mass transfer the mass transfer coefficient varies with diffusion coefficient (D) of the diffusing species as
- OJEE - 2025
- Mass Transfer
- For an incompressible flow, the x and y components of the velocity vector are \( V_x = 2(x+y) \), \( V_y = 3(y+z) \), where x, y, and z are in meters and velocities are in m/s. Then the z component of the velocity vector (V\(_z\)) for the boundary condition \( V_z = 0 \) at \( z = 0 \) is
- OJEE - 2025
- Fluid Mechanics
View More Questions