The Greedy Method is an approach for solving certain types of optimization problems. The greedy algorithm chooses the optimum result at each stage. While this works the majority of the times, there are numerous examples where the greedy approach is not the correct approach. For example, let’s say that you’re taking the greedy algorithm approach to earning money at a certain point in your life. You graduate high school and have two options:
Get a job that only requires a high school diploma
Go to college and then get a job after you graduate from college
The greedy approach would choose the first option. You instantly get money versus spending money to get an education. Although you’re likely to get more money with a college education in the future, the algorithm only examines your choices at that moment. Let’s look at an example of the greedy algorithm in action. We have a directed graph with weighted edges.
If we’re trying to make our way from A to J, the greedy algorithm will examine all the paths that are immediately connected to A, which are edges to B and C. The weight of edge A-C is smaller than A-B, so the algorithm chooses A-C. We’ll keep a table with the greedy and optimal paths during each point. After the first decision, the greedy algorithm is winning. Its current weight is 3 while the current weight of the optimal path is 4.
The greedy algorithm is now at vertex C and has the option to use edge C-F or C-G. It chooses C-G since the immediate weight is lower.
At this point the greedy algorithm is still winning. The weight of the edges utilized by the greedy algorithm totals 6, while the weight of the edges utilized by the optimal path totals 9. The greedy algorithm is now at vertex G. It has only one path to vertex I, so it must take it. It gets a big penalty in weight by adding 12 to its current weight.
The current weight of the greedy algorithm, 18, has now surpassed the weight of the optimal algorithm, 11. The greedy algorithm has one more edge that it can take to J. Unfortunately, it gets another big penalty by adding on an additional weight of 9.
Both the greedy algorithm and the optimal algorithm went from A to J but utilized different paths. In the end, the optimal algorithm won since its total weight was more than twice as less as that of the greedy algorithm. Why would the greedy algorithm even exist then? There are situations that we’ll cover where the greedy algorithm is the most efficient algorithm. Some algorithms that utilize the greedy approach are Kruskal’s algorithm, Prim’s algorithm, and Dijkstra’s algorithm.
