Greedy Algorithms: Dijkstra's Algorithm
Greedy Algorithms
- A greedy algorithm solves an optimization problem by making the best decision at each step. This is known as the locally optimal decision.
- Greedy algorithms are simple and efficient but are NOT always correct.
- In order for a greedy algorithm to work, a problem must satisfy:
- The optimal substructure property
- The greedy property
