About Greedy Algorithm
The cover image generated by ChatGPT.
Introduction
The Greedy Algorithm is an approach that solves problems by choosing the option that appears most favorable at each step. It makes simple and intuitive decisions based on the locally optimal choice among all available options at the moment, with the expectation that these local choices will accumulate into a globally optimal solution, continuing this process until a termination condition is met.
Since the greedy algorithm focuses solely on the current local environment, the solution it produces is not guaranteed to be the global optimum and may even result in a longer path. However, it’s undeniable that because the algorithm does not consider the overall problem space and makes decisions only based on local information, it often delivers high execution efficiency.
How It Works
This example is similar to the one used in Dijkstra’s Algorithm, except here we are not looking for the global shortest path but rather the locally shortest one. As shown in the figure above, let’s assume there are six locations labeled $A$, $B$, $C$, $D$, $E$, and $F$. The task is to find a path from starting point $A$ to destination $F$.
First, we calculate the distances of each path, as shown below:
To find the path from point $A$ to point $F$, we’ll now build a table to record the previous location at each step of the pathfinding process.
| Node | Marked | Previous Node |
|---|---|---|
| A | ||
| B | ||
| C | ||
| D | ||
| E | ||
| F |
Since the starting point is $A$, we mark $A$.
| Node | Marked | Previous Node |
|---|---|---|
| A | ✓ | |
| B | ||
| C | ||
| D | ||
| E | ||
| F |
Next, we evaluate the paths connected to point $A$ that lead to unmarked points $B$ and $C$, looking for the shortest path. Since both paths have the same length, we arbitrarily choose point $B$ for the next step.
We mark point $B$ and record its previous location as $A$.
| Node | Marked | Previous Node |
|---|---|---|
| A | ✓ | |
| B | ✓ | A |
| C | ||
| D | ||
| E | ||
| F |
Now, we continue by evaluating the unmarked points adjacent to point $B$, such as the paths to points $D$ and $E$. We find that the path to point $E$ is shorter, so we mark point $E$ and record it accordingly.
| Node | Marked | Previous Node |
|---|---|---|
| A | ✓ | |
| B | ✓ | A |
| C | ||
| D | ||
| E | ✓ | B |
| F |
Next, we evaluate the unmarked points adjacent to point $E$, such as the paths to points $C$ and $F$. We find that the path to point $C$ is shorter, so we mark point $C$ and record it accordingly.
| Node | Marked | Previous Node |
|---|---|---|
| A | ✓ | |
| B | ✓ | A |
| C | ✓ | E |
| D | ||
| E | ✓ | B |
| F |
Finally, we find that the only unmarked point adjacent to point $C$ is point $F$. After marking point $F$, we obtain the following table.
| Node | Marked | Previous Node |
|---|---|---|
| A | ✓ | |
| B | ✓ | A |
| C | ✓ | E |
| D | ||
| E | ✓ | B |
| F | ✓ | C |
From the table above, we can determine that the shortest path obtained using the greedy algorithm is
$$ A \Rightarrow B \Rightarrow E \Rightarrow C \Rightarrow F, $$
with a total distance of $4 + 5 + 8 + 16 = 33$.
In comparison, the path found using Dijkstra’s Algorithm, $A \Rightarrow B \Rightarrow E \Rightarrow F$, has a much shorter total distance of 18.
However, we can observe that the computational cost under the greedy algorithm is significantly lower. It only needs to compare the immediate cost from the current location to the next, without maintaining global state or repeatedly updating distances.
Therefore, in resource-constrained environments or applications requiring real-time responsiveness, the greedy algorithm still holds value. Even though it cannot guarantee a globally optimal solution, it remains widely used in various approximation approaches.
Algorithm
Based on the above example, the steps of the greedy algorithm can be summarized as follows:
- Starting from the current location, select one of the adjacent, unmarked locations with the best weight or path condition (e.g., minimum weight or maximum benefit).
- Move to that location and mark the path.
- Return to Step 1 and repeat until the termination condition is met (e.g., reaching the destination).
Conclusion
Compared to Dijkstra’s algorithm, which requires updating global information and thus has a relatively high computational cost, the greedy algorithm offers a simpler decision-making process that provides a faster solution strategy without guaranteeing a globally optimal solution. Although it may produce suboptimal results or even take longer routes in some cases, the greedy algorithm often demonstrates efficient performance in scenarios with limited computational resources or real-time response requirements. It is a concise and powerful strategic tool that, while not suitable for all problems, can be effectively applied in appropriate contexts by understanding its characteristics and limitations—striking a balance between speed and solution quality.
References
貪婪演算法. (October 31, 2022). Wikipedia, The Free Encyclopedia. Retrieved July 7, 2025, from https://zh.wikipedia.org/zh-tw/贪心算法
拉爾夫的技術隨筆. (September 6, 2022). 演算法學習筆記：貪婪演算法（Greedy Algorithm）. Medium. Retrieved July 7, 2025, from https://medium.com/@ralph-tech/演算法學習筆記-貪婪演算法-greedy-algorithm-e2666b93d05f
Sean Chou. (August 15, 2024). 演算法筆記系列 — Greedy Algorithm 貪婪演算法. Medium. Retrieved July 7, 2025, from https://medium.com/技術筆記/演算法筆記系列-greedy-algorithm-貪婪演算法-236f509200de
