In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, $n$ and $m$ are number of vertices and edges, respectively. Match each algorithm with its time complexity.
| List I | List II |
|---|
| A. Bellman-Ford algorithm | I. $O(m\log n)$ |
| B. Kruskal's algorithm | II. $O(n^3)$ |
| C. Floyd-Warshall algorithm | III. $O(n*m)$ |
| D. Topological sorting | IV. $O(n+m)$ |
Choose the correct answer from the options given below:
🎥 Video solution / Text Solution of this question is given below:
Bellman-Ford algorithm checks all edges repeatedly for shortest path, so its time complexity is $O(n*m)$. Thus, $A-III$.
Kruskal's algorithm sorts edges and then applies union-find, so its time complexity is $O(m\log n)$. Thus, $B-I$.
Floyd-Warshall algorithm uses three nested loops for all pairs shortest path, so its time complexity is $O(n^3)$. Thus, $C-II$.
Topological sorting visits vertices and edges once, so its time complexity is $O(n+m)$. Thus, $D-IV$.
Final matching is $A-III,\ B-I,\ C-II,\ D-IV$.