Q96.Marks: +2.0UGC NET Paper 2: Computer Science 26th Nov 2021
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity.
List I
List II
Standard graph algorithms
Time complexities
A.
Bellman‐Ford algorithm
I.
O(m*log n)
B.
Kruskal’s algorithm
II.
O(n3)
C.
Floyd‐Warshall algorithm
III.
O(n*m)
D.
Topological sorting
IV.
O(n + m)
Choose the correct answer from the options given below :
1.A ‐ III, B ‐ I, C ‐ II, D ‐ IV✓ Correct
2.A ‐ II, B ‐ IV, C ‐ III, D ‐ I
3.A ‐ III, B ‐ IV, C ‐ I, D ‐ II
4.A ‐ II, B ‐ I, C ‐ III, D ‐ IV
Solution
Solution :
Bellman‐Ford algorithm ( Finds shortest paths from a single source node to all of the other nodes in a weighted digraph ) : O(mn) ,where, n is no of edges , m is no of nodes.
Kruskal’s algorithm (Using Greedy approach it find the minimum cost spanning tree ) - O(m*log n)
Floyd‐Warshall algorithm (Find shortest paths in a directed weighted graph with positive or negative edge weights ) - O(n3)
Topological sorting (Find linear ordering of vertices for Directed Acyclic Graph (DAG) ) - O(n + m)