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 :
- 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 77 students.
Show answer & explanation
Correct answer: B
Correct algorithm descriptions and matching:
Dijkstra's Algorithm → Finds shortest paths from a single source in a weighted graph with non-negative edge weights.
Floyd–Warshall Algorithm → Finds shortest paths between all pairs of vertices; it works with negative edge weights provided there are no negative cycles.
Bellman–Ford Algorithm → Finds shortest paths from a single source and supports negative edge weights; it can also detect negative-weight cycles.
Prim's Algorithm → Finds a minimum spanning tree of a connected weighted undirected graph.
Conclusion: None of the provided answer choices is fully correct because the list of descriptions contains entries that do not correspond to Bellman–Ford or Prim's (one description is a sorting algorithm and another refers to strongly connected components). Therefore no option correctly matches all four algorithms to their proper descriptions.
A video solution is available for this question — log in and enroll to watch it.