Match the columns.

Match List – I with List – II.

	List – I		List – II
A.	Topology sort of DAG	I.	O(V + E)
B.	Kruskal’s MST algorithm	II.	O(VE)
C.	Bellman-Ford’s single-source shortest path algorithm	III.	​$$\theta(V + E)$$​​
D.	Floyd Warshall’s all pair shortest path algorithm	IV.	​$$\theta(V^3)$$​​

Choose the correct option from those given below:

Correct option is C

Let's break down the correct matches between List-I and List-II:
A. Topology sort of DAG
o A topological sort of a Directed Acyclic Graph (DAG) can be done using a depth-first search (DFS) or a BFS. This operation takes time proportional to the number of vertices and edges in the graph.
o Time complexity: O(V + E) where V is the number of vertices and E is the number of edges.
• Correct Match: A → III (O(V + E))
B. Kruskal’s MST algorithm
o Kruskal’s algorithm is a greedy algorithm to find the Minimum Spanning Tree (MST) of a graph. It involves sorting the edges and using a disjoint-set data structure to check for cycles.
o Time complexity: Sorting takes O(E log E) and union-find operations take O(E), leading to an overall complexity of O(E log V).
o For dense graphs, this is often expressed as O(VE).
• Correct Match: B → I (O(VE))
C. Bellman-Ford’s single-source shortest path algorithm
o Bellman-Ford is used to find the shortest path from a single source vertex to all other vertices. The algorithm iterates over all the edges for V - 1 times, where V is the number of vertices.
o Time complexity: O(VE), where V is the number of vertices and E is the number of edges.
• Correct Match: C → II (O(VE))
D. Floyd Warshall’s all pair shortest path algorithm
Floyd-Warshall is used to find the shortest paths between all pairs of vertices. It is a dynamic programming algorithm with a time complexity of $$\bf{O(V^3)}$$​ because it has to consider all pairs of vertices for every vertex.
• Correct Match: D → IV $$\bf{(\theta(V^3))}$$​​
Information Booster:
1. Topology Sort of DAG:
o Used for tasks like scheduling, ordering of tasks based on dependencies, etc.
o Time complexity is O(V + E), making it efficient for sparse graphs.
2. Kruskal's Algorithm:
o A greedy algorithm for finding the Minimum Spanning Tree (MST).
o Efficient for edge-dense graphs, as its complexity depends more on the number of edges than the vertices.
3. Bellman-Ford Algorithm:
o Can handle graphs with negative weights, unlike Dijkstra's algorithm.
o Its ability to detect negative-weight cycles makes it particularly useful in certain applications, such as in currency exchange problems.
4. Floyd-Warshall Algorithm:
o A dynamic programming solution to find shortest paths between all pairs of vertices.
o Suitable for dense graphs, but its cubic time complexity makes it inefficient for large graphs.
Additional Knowledge:
• Kruskal's Algorithm: O(E log E) is the dominant factor in its time complexity. It works well with sparse graphs where E is much greater than V.
• Bellman-Ford Algorithm: O(VE), where E is the number of edges and V is the number of vertices. It's less efficient than Dijkstra's but can handle negative weights.
• Floyd-Warshall Algorithm: Best for computing all-pairs shortest paths in dense graphs. Its time complexity $$\bf{O(V^3)}$$​ might not be optimal for graphs with a large number of vertices.