COMP9123 — Week 9
Foundations & proof moves
Week 9 foundations are about the invariants behind greedy graph optimization: when a relaxation is trustworthy, why Dijkstra's greedy commitment works, how edge-weight transformations change optimization problems, and why the cut property makes MST choices safe.
Relaxation Invariants: Tentative Labels Are Upper Bounds Until Proven Final
The safest way to think about shortest-path labels is this: before a vertex is settled, its label is a current best claim, not yet a mathematical guarantee of optimality. Relaxation only ever lowers that claim when a better route is discovered.
If you know a route to u of cost D[u], then traversing one more edge \((u,v)\) gives a candidate route to v of cost D[u] + w(u,v). Comparing that candidate to D[v] is exactly what relaxation means.
If a full path is shortest, then every prefix of that path must already be shortest to its endpoint. Otherwise the whole path could be improved by replacing a bad prefix with a better one.
Dijkstra Reasoning: Where Correctness and Runtime Both Come From
The lecture separates Dijkstra into two stories: a correctness story about why the smallest label can be safely settled, and a runtime story about how graph scanning and priority-queue operations contribute differently.
| Part of the algorithm | Why it matters |
|---|---|
| Initialization | Sets the source label to 0, all others to infinity, and makes the predecessor relation meaningful from the start. |
remove_min |
This is the greedy commitment step, where the next vertex becomes final. |
decrease_key |
This is how improved relaxations are reflected in the queue ordering. |
| Adjacency scans | Across the whole algorithm they sum to \(O(m)\), which is why the queue implementation becomes the key complexity lever. |
The lecture's directed-graph note is important. Dijkstra still works for directed graphs as long as weights are non-negative. What changes is the path structure and which outgoing edges are available for relaxation, not the core greedy logic or runtime shape.
Weight Transforms: Shortest Paths and MSTs React Differently
The tutorial's transformation problem is one of the best conceptual exercises in the week. It forces you to separate “what preserves local edge order?” from “what preserves total path cost?”
| Transformation | Shortest paths | MSTs |
|---|---|---|
| \(w_1(e)=\alpha w(e)\) with \(\alpha > 0\) | Preserved, because every path weight is scaled by the same positive factor. | Preserved, because every tree weight is scaled by the same positive factor. |
| \(w_2(e)=w(e)+\beta\) with \(\beta > 0\) | Not preserved in general, because paths with more edges pay the extra cost more times. | Preserved, because every spanning tree has exactly \(n-1\) edges and receives the same total additive shift. |
| \(w_3(e)=w(e)^2\) | Not preserved in general, because squaring can change which multi-edge path has the smaller sum. | Preserved when weights are positive, because squaring keeps the edge order and MST selection depends on edge-order comparisons. |
This is a beautiful contrast: shortest paths care about sums along one route, while MSTs care about which individual edges are safe across cuts and cycles. That is why the same transformation can affect one problem but not the other.
MST Exchange Proof: Why the Cheapest Crossing Edge Is Safe
The cut property is the backbone of MST correctness proofs. The lecture presents it as a structural fact, but the proof move to remember is an exchange argument: add a supposedly safe edge, find a cycle, and swap out something no better.
Take any MST that does not already include the cheapest edge crossing a chosen cut.
Adding that cheapest crossing edge creates a cycle. Because the cycle crosses the cut, it must also contain some other edge crossing the same cut.
Swap out the other crossing edge. Since the chosen edge was the cheapest one crossing the cut, total cost does not increase, so there exists an MST containing it.
Tutorial Applications: Modeling Tricks Matter as Much as Core Algorithms
The later tutorial problems are really modeling exercises. They ask whether you can reshape an optimization goal into one of the known frameworks from the lecture.
| Problem | Main idea |
|---|---|
| Tie-break shortest paths by fewest edges | Modify edge lengths to prioritize total cost first and edge count second. |
| Vertex-cost path problem | Re-express the path objective so vertex costs are absorbed into a standard shortest-path computation. |
| Improving-mst / reverse-mst | Use cycle and cut logic to argue that repeated local improvements converge to an MST. |
| Bandwidth matrix | Compute all-pairs bottleneck values in cubic time by dynamic-programming-style reasoning or equivalent graph structure. |
| Libraries and roads challenge | Model cities as graph vertices and candidate roads as edges, then reason about connected components and connection cost. |
How to review this page well
The three checks are inline on purpose. They live under the subpath property, the weight-transformation comparison, and the MST cut proof so you can repair exactly the right idea instead of re-reading the whole chapter.
Tutorial review
Do the tutorial after the study guide. Week 9 becomes much easier once you already know which problems are shortest-path flavored and which ones are MST flavored.
Week 9 checklist. You should be able to explain the relaxation update, state exactly why Dijkstra needs non-negative edges, distinguish shortest-path objectives from MST objectives, compare how scaling or shifting weights affects each problem, and describe why Prim and Kruskal are both safe greedy algorithms for the same MST target.