Match List I with List II List - I (Algorithm) List - II (Description) (A)…
2024
Match List I with List II
List - I (Algorithm) List - II (Description)
(A) Dijkstra's Algorithm (I) Find the shortest path between all pairs of vertices in a graph with positive or negative edge weights.
(B) Floyd-Warshall Algorithm (II) Finds the shortest path in a weighted graph with non-negative edge weights.
(C) Bellman-Ford Algorithm (III) Sort elements by repeatedly moving them post neighbouring elements that are smaller.
(D) Prim's Algorithm (IV) Determines the strongest connected components in a directed graph.
Choose the correct answer from the options given below :
Answer: B. (A)-(II), (B)-(I), (C)-(IV), (D)-(III) — Concept Graph algorithms that compute distances split into different problem types with different edge-weight-sign tolerance, plus a completely separate…
- A.
(A)-(II), (B)-(I), (C)-(III), (D)-(IV)
- B.
(A)-(II), (B)-(I), (C)-(IV), (D)-(III)
- C.
(A)-(I), (B)-(II), (C)-(III), (D)-(IV)
- D.
(A)-(III), (B)-(II), (C)-(IV), (D)-(I)
Attempted by 100 students.
Show answer & explanation
Correct answer: B
Concept
Graph algorithms that compute distances split into different problem types with different edge-weight-sign tolerance, plus a completely separate problem — building a minimum spanning tree:
Single-source shortest path (SSSP): the distance from ONE fixed source vertex to every other vertex.
All-pairs shortest path (APSP): the distance between EVERY pair of vertices at once.
Minimum spanning tree (MST): connects all vertices with the least total edge weight — this is not a shortest-path problem at all.
Within SSSP, some algorithms require non-negative edge weights; others tolerate negative weights and can additionally detect negative-weight cycles.
Applying it here
Algorithm | Actual behaviour |
|---|---|
Dijkstra's Algorithm | SSSP, restricted to non-negative edge weights — matches description (II). |
Floyd–Warshall Algorithm | APSP, tolerates positive or negative edge weights (with no negative cycle) — matches description (I). |
Bellman–Ford Algorithm | SSSP that tolerates negative edge weights and detects negative-weight cycles. |
Prim's Algorithm | Builds a minimum spanning tree of a connected weighted undirected graph. |
So (A)-(II) and (B)-(I) are unambiguous matches from the standard definitions of Dijkstra's and Floyd–Warshall's algorithms. Descriptions (III) and (IV) are a different case: (III) describes a comparison-sort step (moving an element past smaller neighbours) and (IV) describes strongly-connected-component detection — neither is a correct definition of ANY of the four listed algorithms, under any assignment. They are decoy descriptions, not a genuine (if misplaced) match for Bellman–Ford or Prim's.
Cross-check
This is a defective official-key item: no offered option is fully correct under the standard algorithm definitions, so the exam final answer key is the scoring authority. This exact question is a UGC NET (Computer Science, August 2024) previous-year item. Because (III) and (IV) do not correctly define any of the four algorithms, the (C)-(D) assignment cannot be settled by algorithm definitions alone — it has to be settled by the exam's own released answer. NTA's officially released answer key marks (A)-(II), (B)-(I), (C)-(IV), (D)-(III) as the correct match for this item. Because this mismatch exists in the exam's own released question and is not something we can silently correct by rewriting the list, the answer here is retained exactly per the official key rather than swapped to a different, equally unverifiable pairing.
Answer
(A)-(II), (B)-(I), (C)-(IV), (D)-(III) — the pairing keyed by NTA.
A video solution is available for this question — log in and enroll to watch it.