Solution

The Correct answer is Option 2

Key Points

Dijkstra's Algorithm:

• Dijkstra's algorithm is a **Greedy algorithm** used to find the shortest path from a source node to all other nodes in a graph.
• It works by selecting the node with the smallest tentative distance, updating its neighbors, and repeating the process until all nodes are visited.
• This greedy approach ensures that the algorithm always chooses the locally optimal solution at each step to eventually find the globally optimal solution.

Kruskal's Algorithm:

• Kruskal's algorithm is a **Greedy algorithm** used to find the Minimum Spanning Tree (MST) of a graph.
• It works by sorting all edges in ascending order of weights and repeatedly adding the smallest edge to the MST if it doesn't create a cycle.
• The greedy strategy ensures that the algorithm picks the best edge at each step, leading to the overall optimal solution for the MST.

Huffman Coding:

• Huffman coding is a **Greedy algorithm** used for lossless data compression.
• It builds a prefix-free binary tree by repeatedly selecting the two smallest frequency nodes and combining them into a new node.
• The greedy approach ensures that the algorithm minimizes the average length of the encoded data, achieving optimal compression.

Bellman-Ford Algorithm:

• Bellman-Ford algorithm is **NOT a Greedy algorithm**. It uses Dynamic Programming to find the shortest path from a source node to all other nodes in a graph.
• It works by relaxing all edges repeatedly, allowing it to handle graphs with negative edge weights.
• Unlike greedy algorithms, Bellman-Ford does not make locally optimal choices at each step.