Match the following:
(A) Floyd Warshall — (i) shortest path between two vertices
(B) Dijkstra — (ii) single source shortest path
(C) Kruskal's — (iii) Minimum spanning tree
(D) Bellman ford — (iv) solving all pair shortest path
(A)-(iii), (B)-(ii), (C)-(iv), (D)-(i)
(A)-(iv), (B)-(i), (C)-(iii), (D)-(ii)
(A)-(i), (B)-(ii), (C)-(iii), (D)-(iv)
(A)-(ii), (B)-(iii), (C)-(i), (D)-(iv)
ANSWER
The correct matching is (A)-(iv), (B)-(i), (C)-(iii), (D)-(ii), which is option (b).
Official answer: BSource: ISRO's revised and final answer key of 16 February 2024
Floyd-Warshall computes shortest paths between every pair of vertices by dynamic programming over intermediate vertices, so (A) matches (iv), solving all pair shortest path.
Kruskal's algorithm sorts the edges by weight and adds each edge that does not form a cycle (checked with union-find), so (C) matches (iii), Minimum spanning tree.
Option (a) has (A)-(iii), option (c) has (A)-(i) and option (d) has (A)-(ii), all wrong. Only option (b) has (A)-(iv). It also has (C)-(iii), so (b) is the only option consistent with both facts.
That leaves Dijkstra and Bellman-Ford for (i) and (ii). Both are single-source algorithms, so the two descriptions overlap. Dijkstra is the one that is naturally run for one target: it can stop as soon as the target vertex is settled, which gives the shortest path between two vertices. Bellman-Ford relaxes all edges times and is the standard single source shortest path algorithm, which also handles negative edge weights. This gives (B)-(i) and (D)-(ii), as in option (b).
Option (a) is wrong because it gives Floyd-Warshall the spanning-tree role and Kruskal's the all-pair role. Option (c) is wrong because it gives Floyd-Warshall (i) and Bellman-Ford (iv). Option (d) is wrong because it gives Floyd-Warshall (ii) and Kruskal's (i).
KEY IDEA
Match each algorithm to its defining problem: Floyd-Warshall solves all pair shortest paths, Kruskal's builds a minimum spanning tree, and Dijkstra and Bellman-Ford are single-source methods. Fix the two unambiguous matches first and use them to eliminate options.
WATCH OUT FOR
Pairing Dijkstra with single source shortest path and Bellman-Ford with the two-vertex form, which gives option (c)-like matchings. Fixing Floyd-Warshall with all pairs and Kruskal's with spanning tree removes every other option.
From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 2 ISRO Graph algorithms questions, with notes
