Match the columns.

Match List - I with List – II.

List - I	List - II
A.	Dijkstra’s Algorithms	I.	Find the shortest path between all pairs of vertices in a graph with positive or negative edge weights.
B.	Floyd-Warshall Algorithms	II.	Finds the shortest path in a weighted graph with non-negative edge weights.
C.	Bellman-frod Algorithms	III.	Sorts elements by repeatedly moving them post neighboring elements that are smaller.
D.	Prim’s Algorithms	IV.	Determines the strongest connected components in a directed graph.

Choose the correct answer from the options given below:

Correct option is B

The algorithms correspond to:
A. Dijkstra’s Algorithm: Finds the shortest path in graphs with non-negative weights.
B. Floyd-Warshall Algorithm: Finds the shortest path between all pairs of vertices in a graph with positive or negative edge weights.
C. Bellman-Ford Algorithm: Handles negative weight edges and can detect negative cycles.
D. Prim’s Algorithm: A greedy algorithm used to find the Minimum Spanning Tree (MST) in a graph.
Information Booster:
1. Dijkstra’s Algorithm: Fastest in weighted graphs with non-negative weights but fails with negative weights.
2. Floyd-Warshall Algorithm: Handles graphs with negative weights and efficiently finds the shortest path for all pairs.
3. Bellman-Ford Algorithm: Slower than Dijkstra but can manage negative weights, making it suitable for specific applications.
4. Prim’s Algorithm: Creates an MST by progressively adding edges that connect the least costly adjacent vertex.
Additional Knowledge:
· Dijkstra’s Algorithm assumes non-negative weights, so it is not used in graphs with negative weights.
· Floyd-Warshall Algorithm is primarily used in dense graphs since it checks every possible pair of vertices.