Match List-I with List-II: \(\begin{array}{cccc} {} & \text{List-I} & {} &…
2019
Match List-I with List-II:
\(\begin{array}{cccc} {} & \text{List-I} & {} & \text{List-II} \\ (a) & \text{Prim’s algorithm} & (i) & O(V^3 \log V) \\ (b) & \text{Dijkstra’s algorithm} & (ii) & O(VE^2) \\ (c) & \text{Faster all-pairs shortest path} & (iii) & O(ElgV) \\ (d) & \text{Edmonds-Karp algorithm} & (iv) & O(V^2) \\ \end{array}\)
Choose the correct option from those options given below:
- A.
\((a) – (ii); (b)-(iv); (c)-(i); (d)-(iii) \) - B.
\((a) – (iii); (b)-(iv); (c)-(i); (d)-(ii) \) - C.
\((a) – (ii); (b)-(i); (c)-(iv); (d)-(iii) \) - D.
\((a) – (iii); (b)-(i); (c)-(iv); (d)-(ii)\)
Attempted by 34 students.
Show answer & explanation
Correct answer: B
Correct matching and explanation:
Prim’s algorithm → O(E log V): Using a binary heap (priority queue) to pick the next minimum-weight edge yields O(E log V) (or O(E + V log V)).
Dijkstra’s algorithm → O(V^2): The simple dense-graph implementation using an array for the distance selection runs in O(V^2). (With a heap it can be O(E + V log V).)
Faster all-pairs shortest path → O(V^3 log V): A faster APSP approach that uses repeated min-plus matrix multiplications (each multiplication O(V^3)) with O(log V) multiplications gives O(V^3 log V).
Edmonds–Karp algorithm → O(VE^2): The Edmonds–Karp implementation of Ford–Fulkerson uses BFS for augmenting paths and runs in O(VE^2).
Therefore the matching is: Prim’s → O(E log V); Dijkstra’s → O(V^2); Faster all‑pairs shortest path → O(V^3 log V); Edmonds–Karp → O(VE^2).
A video solution is available for this question — log in and enroll to watch it.