Q88.Marks: +2.0UGC NET Paper 2: Computer Science 11 March 2023
Match List I with List II
LIST - I
LIST - II
A.
Dijkstra's Algorithm
I.
Calculates path matrix
B.
Prim's Algorithm
II.
Stores minimum cost edge
C.
Warshall's Algorithm
III.
Stores the total cost from a source node to the current node
D.
Kruskal's algorithm
IV.
Finds Minimum Spanning Tree
Choose the correct answer from the options given below:
1.A - I, B - II, C - III, D - IV
2.A - III, B - II, C - I, D - IV✓ Correct
3.A - II, B - I, C - IV, D - III
4.A - III, B - IV, C - II, D - I
Solution
The correct answer is A - III, B - II, C - I, D - IV
Key PointsThe correct match for each algorithm to its description is as follows:
Dijkstra's Algorithm - III. Stores the total cost from a source node to the current node: Dijkstra's Algorithm is used to find the shortest paths from a source node to all other nodes in a weighted graph. It uses a data structure, often a priority queue, to keep track of the minimum distance from the source node to each node in the graph.
Prim's Algorithm - II. Stores minimum cost edge: Prim's Algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph. It works by adding the smallest edge that connects a vertex from the growing minimum spanning tree to a vertex outside the tree.
Warshall's Algorithm - I. Calculates path matrix: Warshall's Algorithm is used to find the transitive closure of a directed graph. It determines the reachability between pairs of vertices in a graph and represents the results in the form of a path matrix.
Kruskal's algorithm - IV. Finds Minimum Spanning Tree: Kruskal's Algorithm is also used to find the minimum spanning tree of a connected, undirected graph. It works by sorting all the edges in ascending order of their weights and adding them to the growing minimum spanning tree as long as they do not form a cycle.
