A **greedy algorithm** is a type of algorithmic paradigm that follows the problem-solving heuristic of making locally optimal choices at each stage with the hope of finding a global optimum.

• In other words, a greedy algorithm makes the best possible decision at each step without worrying about the consequences in the future. This approach is known as the **greedy choice property**.

## Examples of Greedy Algorithms:

**Dijkstra’s Algorithm:**

Used to find the shortest path from a source vertex to all other vertices in a weighted graph. At each step, it selects the vertex with the minimum distance.

**Kruskal’s Algorithm:**

Finds the minimum spanning tree of a connected, undirected graph. It repeatedly adds the edge with the smallest weight, avoiding cycles.

**Prim’s Algorithm:**

Similar to Kruskal’s, Prim’s algorithm builds a minimum spanning tree by adding the edge with the smallest weight at each step.

**Fractional Knapsack:**

Given a set of items, each with a weight and a value, the goal is to maximize the total value of items in a knapsack of limited capacity. The greedy choice is to select items with the maximum value-to-weight ratio.

**Huffman Coding:**

Used for lossless data compression. It builds an optimal binary tree for encoding characters by assigning shorter codes to more frequent characters.

**Activity Selection:**

In a set of activities with start and finish times, the goal is to select the maximum number of non-overlapping activities. The greedy choice is to select the activity that finishes first.