COMP90038 · Algorithms And Complexity
Greedy Algorithms
The last paradigm: build a solution by repeatedly taking the locally best choice available right now and never reconsidering — fast and simple, but only correct when the problem has the right structure, which is the chapter's recurring theme. Three classic greedy algorithms earn their bounds. Prim's algorithm grows a minimum spanning tree by always adding the cheapest edge leaving the tree (a priority queue gives O(E log V)). Dijkstra's algorithm finds single-source shortest paths on non-negative weights by always settling the closest unsettled vertex next, plus the super-source trick for nearest-of-k queries. Huffman coding builds an optimal prefix code by repeatedly merging the two least-frequent symbols. The chapter is equally clear about when greedy is wrong — 0/1 knapsack and shortest paths with negative edges both defeat the greedy choice — so you learn to justify a greedy choice (an exchange argument) rather than assume it. Q1 hand-traces a Prim/Dijkstra run or an MST weight, and Q3–Q10 ask you to design with a greedy choice and argue it is safe.
What this chapter covers
- 01The greedy strategy: locally best, never reconsidered
- 02Prim's MST — cheapest edge leaving the tree, O(E log V)
- 03Dijkstra's shortest paths (non-negative weights); the super-source trick
- 04Huffman coding — merge the two least-frequent symbols
- 05When greedy fails (0/1 knapsack, negative edges) and how to justify it
Worked example: one Dijkstra relaxation step
- +1Settle the closest unsettled vertex. Among unsettled vertices, a has the smallest tentative distance (3), so settle a — its distance 3 is now final.
- +2Relax a's outgoing edge a→b (weight 2). Candidate: dist(a) + 2 = 3 + 2 = 5, compared with the current dist(b) = 7.
- +1Update. 5 < 7, so dist(b) is lowered to 5 (path s→a→b).
Key terms
- Greedy algorithm
- Builds a solution by repeatedly making the locally optimal choice and never undoing it. Fast and simple, but correct only when the problem has a matching structure (matroid / exchange property); otherwise it can return a sub-optimal answer.
- Minimum spanning tree (MST)
- A subset of a connected weighted graph's edges that links all vertices with no cycle and minimum total weight. Built greedily by Prim (grow from a vertex) or Kruskal (add cheapest safe edges).
- Prim's algorithm
- Grows an MST by repeatedly adding the cheapest edge connecting the tree to a vertex outside it, using a priority queue to find that edge. O(E log V) with a binary heap; the greedy choice is provably safe (cut property).
- Dijkstra's algorithm
- Single-source shortest paths on non-negative edge weights: repeatedly settle the closest unsettled vertex and relax its edges. O(E log V) with a heap; it fails on negative edges because a settled vertex might later be improved.
- Huffman coding
- An optimal variable-length prefix code built greedily: repeatedly merge the two lowest-frequency symbols into a subtree until one tree remains. Frequent symbols get short codes, minimising the expected encoded length.
Greedy Algorithms FAQ
When is a greedy algorithm guaranteed correct?
When the problem has optimal substructure and the greedy-choice property: a locally optimal choice is always part of some globally optimal solution. Prim, Dijkstra (non-negative weights) and Huffman satisfy this and have exchange-argument proofs; 0/1 knapsack and negative-weight shortest paths do not.
Why does Dijkstra fail on negative edges?
Because Dijkstra settles a vertex's distance as final the moment it is the closest unsettled one, assuming no later path can be cheaper. A negative edge can make a longer-looking route cheaper after the fact, so a settled distance becomes wrong. Use Bellman-Ford (or, for all pairs, Floyd) when edges can be negative.
What is the super-source trick?
To answer a nearest-of-k or multi-source query in one shot, add a virtual super-source connected with zero-weight edges to all k sources, then run a single Dijkstra from it. The result gives each vertex its distance to the closest of the k originals without running Dijkstra k times.
Exam move
Hand-trace Prim and Dijkstra runs until they are automatic, because Q1 asks for an MST weight or a shortest-path settle order and Q3–Q10 ask you to design with a greedy choice. The marks in design questions are in the justification: argue the greedy choice is safe (an exchange argument) rather than asserting it, and know the standard counterexamples where greedy fails (0/1 knapsack, negative-edge shortest paths) so a Q2 True/False on “greedy always works” is an easy refute. Keep Prim, Dijkstra and Huffman's priority-queue bound (O(E log V)) at your fingertips.
