Match List I with List II. List I: (a) Prim's algorithm, (b) Dijkstra's algorithm, (c) Faster all-pairs shortest path, (d) Edmonds-Karp algorithm. List II: (i) O(V³ lg V), (ii) O(VE²), (iii) O(E lg V), (iv) O(V²).

1. A(a)-(ii); (b)-(iv); (c)-(i); (d)-(iii)
2. B(a)-(iii); (b)-(iv); (c)-(i); (d)-(ii)
3. C(a)-(ii); (b)-(i); (c)-(iv); (d)-(iii)
4. D(a)-(iii); (b)-(i); (c)-(iv); (d)-(ii)

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

Show answer & explanation

Correct answer: B. (a)-(iii); (b)-(iv); (c)-(i); (d)-(ii)

Explanation

Prim (binary heap) is O(E lg V); Dijkstra with an array is O(V²); repeated-squaring all-pairs is O(V³ lg V); Edmonds–Karp is O(VE²).