GATE 2013
April 5, 2025GATE 2013
April 5, 2025GATE 2013
| Question 19 |
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
| Θ(n2) | |
| Θ(n2 log n) | |
| Θ(n3) | |
| Θ(n3 log n) |
Question 19 Explanation:
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)
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)
Correct Answer: C
Question 19 Explanation:
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)
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)