Follow Us :

DT Q46

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

  • Option : C
  • Explanation :
    Given: A complete graph on n vertices?
    To find: Time complexity of Bellman-Ford Single source shortest path.
    Analysis: Time complexity of Bellman-ford algorithm on a graph with n vertices and m edges is O(nm) For a complete graph, m = nC2 = 0(n2) (Since, there is an edge between all pair of vertices)
    ∴ Time Complexity = 0(n2.n) = 0(n3)
    ∴ Solution is (C)
    Note : Include vertex of degree zero in even degree vertices.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *