Greedy Algorithms

AA greedy algorithm builds a solution one step at a time, always taking whichever choice looks best right now, and never reconsidering that choice later. That sounds like a reckless way to solve anything — and for many problems, it is — but for a specific, identifiable class of problems, the locally best choice at every step provably leads to a globally optimal solution.

When Greedy Works — and When It Doesn't

AA problem is greedy-solvable when it has two properties together: the greedy-choice property (a locally optimal choice at each step is always part of some globally optimal solution, so committing to it never rules out reaching the best overall answer) and optimal substructure (an optimal solution to the whole problem contains optimal solutions to its subproblems). Both have to hold — optimal substructure alone isn't enough, because it's also a requirement for dynamic programming, which exists precisely to handle problems where the greedy-choice property fails.

The 0/1 knapsack problem is the standard counter-example that makes this concrete: given a knapsack with limited capacity and a set of items each with a weight and a value, choose which items to pack to maximise total value without exceeding capacity. Greedily taking the item with the best value-to-weight ratio first can strand the knapsack with leftover capacity too small for any other whole item, while a different, less locally-attractive first choice might have left room for a combination worth more overall — the locally best choice at step one doesn't guarantee it belongs to the globally best solution, so 0/1 knapsack needs dynamic programming, not greedy, to solve exactly.

Dijkstra's Shortest-Path Algorithm

Dijkstra'sDijkstra's algorithm finds the shortest path from a single source node to every other node in a graph with non-negative edge weights, and it's greedy in a precise sense: it repeatedly picks the unvisited node with the smallest known distance so far, and commits to that distance as final¹. Walk it through on a small graph — A connects to B (weight 4) and C (weight 1); C connects to B (weight 1) and D (weight 5); B connects to D (weight 1):

Start: dist(A)=0, all others = infinity
Visit A: relax neighbours -> dist(B)=4, dist(C)=1
Visit C (smallest unvisited, 1): relax -> dist(B)=min(4, 1+1)=2, dist(D)=1+5=6
Visit B (smallest unvisited, 2): relax -> dist(D)=min(6, 2+1)=3
Visit D (smallest unvisited, 3): done
Final: A=0, B=2, C=1, D=3

The greedy-choice property holds here specifically because edge weights are non-negative: once a node's shortest distance is finalised, no path discovered later could possibly improve it, because any such path would have to go through an already-visited node with a strictly larger recorded distance plus more positive weight on top — which can only make the total larger, never smaller. Allow negative edge weights and this guarantee breaks (a longer-looking path might later turn out shorter via a negative edge), which is exactly why Dijkstra's algorithm is specified for non-negative weights only, and a different algorithm (Bellman-Ford) is needed when negative weights are possible.

Minimum Spanning Trees: Kruskal's Algorithm

AA minimum spanning tree (MST) connects every node in a graph using the minimum possible total edge weight, with no cycles. Kruskal's algorithm builds one greedily: sort every edge by weight, then process edges from lightest to heaviest, adding each edge to the growing forest unless it would create a cycle (which is checked efficiently with a union-find/disjoint-set structure that tracks which nodes are already connected to each other)². On the same graph above (edges A-B:4, A-C:1, C-B:1, C-D:5, B-D:1), sorted by weight: A-C(1) — add; C-B(1) — add; B-D(1) — add; A-B(4) — would connect A and B, but they're already connected via A-C-B, so skip (it would create a cycle); C-D(5) — add (D isn't connected yet). Final MST: A-C, C-B, B-D, C-D, total weight 1+1+1+5 = 8.

The dotted A-B edge above is the one Kruskal's algorithm skips — every node is already reachable without it, so including it would only add weight for no connectivity gained.

Prim's algorithm reaches the same guaranteed-optimal answer from a different angle — starting from one node and always growing the tree by its single cheapest connecting edge to any node not yet in the tree, rather than considering all edges globally sorted by weight — and is often the better practical choice on a dense graph, where Kruskal's up-front global sort becomes the bottleneck.

References