Match List I with List II. List I: A. Topological sort of a DAG, B. Kruskal's MST algorithm, C. Bellman-Ford single-source shortest path, D. Floyd-Warshall all-pairs shortest path. List II: I. O(V + E), II. O(VE), III. θ(V + E), IV. θ(V³).

1. AA-I, B-III, C-IV, D-II
2. BA-III, B-I, C-IV, D-II
3. CA-III, B-I, C-II, D-IV
4. DA-I, B-III, C-II, D-IV

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A-III, B-I, C-II, D-IV

Explanation

Topological sort is Θ(V + E), Bellman–Ford O(VE), Floyd–Warshall Θ(V³), leaving O(V + E) for Kruskal in the key's matching.

Note: Kruskal's algorithm actually runs in O(E log V); the official key pairs it with O(V + E).