Greedy Algorithm | Dijkstra Algorithm

Greedy algorithm only applies to the optimization problem.

Greedy algorithm makes the decision at every point choosing the local minimum or maximum depending on the optimization type.

Here we want to find shortest path from S to E

This is how the greedy algorithm works:

1. Starting From vertex (S):
2. To get to A paying 4
3. To get to B paying 2
4. Since this is shortest path optimization type, i will be greedy & go to B
5. At vertex (B):
6. I can go to D by paying 10
7. Or i can go to C by paying 3
8. Thus i will go to (C)
9. At vertex (C), i will then go to (E) by paying 4
10. Total : 2 + 3 + 4 = 9, thus the shortest path.

But the greedy algorithm does not work all the time for example:

On changing the value from (A) => (C), greedy algo does not work

from S -> B -> C -> E  = 2 + 6 + 4  = 12
wheras S -> A -> C -> E = 4 + 1 + 4 = 9

thus greddy algorithm fails

If we take the concept of the greedy algorithm and figure out how to utilize in a way that cover the weakness of this algorithm, it turns into Dijkstra's algorithm

Here how we approach Dijkstra algorithm:

1. We keep track of the distance array
2. Distance to all the other nodes are Infinity, because we don't know the distance yet.
3. It doesn't take any distance to reach itself so we put 0 for the starting node
4. We then figure out the distance from this node to all the other nodes
5. If we can travel to that node we take the distance and input in our array
6. if we can't travel we don't update the array

if we are looking for the shortest path, then there are two optimal algorithms that we automatically know are proabably going to be the correct way to appraoch the problem

################## Point to be noted #############################

When you see a directed weighted graph and you are looking for the shortest path to all the nodes from any specific node,

you want to use these two algorithms that we are going to learn.

Dijkstra Algorithm:

-------------------

Dijkstra algo can only be applied to graphs that are directed and weighted.

It aims to help you figure out, what is the shortest distance between some node of your choice to every other node

Greedy method is an algorithmic paradigm, meaning it's a way that we tackle problems that is very simple. it only applies when we are working with optimization problem

Optimization problems are problems where you are looking for max possible value or min possible value

and that's all greedy method aims to help you solve, and is the simplest, most intuitive way

Greedy Algorithm :

We are hiking on a trail, we come to a form , left which take 4 hrs and right which take 1 hour.

           4 hour 
         /
        /
 Here -
        \
         \
         1 hour

        We take 1 hour obviously

we take the right path, that's all greedy algorithm does,

it just says that if i have to make a decision between all my options, i want to pick the one that most logically gets me to my optimal solution

Minimum Optimization => shortest path => take the short way 

Maximum Optimization => longest path => takes the longest way

Greedy algorithms are commonly used for optimization problems like:

1. Scheduling/Interval Problems
2. Activity Selection (selecting max non-overlapping activities)
3. Meeting Room Allocation
4. Job Sequencing with Deadlines
5. Packing Problems
6. Fractional Knapsack (can take fractions of items)
7. Bin Packing
8. Container Loading
9. Graph Problems
10. Minimum Spanning Tree (Prim's, Kruskal's)
11. Minimum Path (Dijkstra's for non-negative weights)
12. Graph Coloring
13. Resource Allocation
14. Task Assignment
15. Resource Distribution
16. Load Balancing

Activity Scheduling:

Activities: 
A1: (1,4)  |-------|
A2: (3,5)      |-----|
A3: (0,6)  |------------|

Greedy Indicator: "Maximum non-overlapping activities"
- Optimization: Maximize activities
- Local Choice: Pick earliest ending activity
- No backtracking needed

Fractional Knapsack:

Items:        Value/Weight Ratio
$60/10kg  =   $6/kg
$100/20kg =   $5/kg
$120/30kg =   $4/kg

Greedy Indicator: "Maximum value within capacity"
- Optimization: Maximize value
- Local Choice: Best value/weight ratio first

Coin Change:

$43 = 25 + 10 + 5 + 1 + 1 + 1

Greedy Indicator: "Minimum coins needed"
- Optimization: Minimize coins used
- Local Choice: Largest possible coin at each step

Example keywords:

Maximize profit
Minimize cost
Find shortest
Select best at each step
Earliest deadline
Highest priority