COMP9123 — Data Structures & Algorithms
Week 9: Graph Algorithms
Week 9 turns graph traversal into optimization. The lecture first studies weighted shortest paths through relaxation and Dijkstra, then pivots to minimum spanning trees and shows how Prim and Kruskal apply greedy reasoning in two different ways.
A strong Week 9 answer keeps the objectives separate: shortest paths optimize route cost from one source, while MSTs optimize total connection cost for the whole graph.
Shortest Paths: Weighted Graphs Add Cost to the Traversal Story
Week 8 gave you shortest paths in unweighted graphs via BFS layers. Week 9 generalizes that idea to weighted graphs, where each edge has a numerical cost, distance, or travel time. Now the path with the fewest edges may not be the cheapest path at all.
| Idea | What the lecture says | Why it matters |
|---|---|---|
| Weighted graph | Each edge carries a real-valued weight representing cost, distance, or some other penalty. | Traversal order alone no longer reveals the optimal route. |
| Shortest path | The path weight is the sum of its edge weights, and we seek the minimum total. | This is the optimization target behind routing and navigation examples. |
| Subpath property | Every subpath of a shortest path is itself shortest between its endpoints. | This is the structural fact that makes all shortest-path algorithms possible. |
| Shortest-path tree | From one source vertex, the chosen predecessor edges form a tree of optimal routes. | The output is not just distances; it is also a recoverable route system. |
Why BFS is no longer enough
BFS treats every edge as one hop. As soon as weights differ, “fewest edges” and “cheapest total weight” split apart.
Professor move
The shortest-path tree slide is not extra notation. It is the lecture showing you that single-source shortest paths produce a reusable global structure, not just one answer for one destination.
Good sanity check
If two candidate routes share a prefix, you should immediately ask whether that prefix is itself optimal. If not, the full route cannot be optimal either.
Relaxation: The Core Local Update Behind Shortest-Path Algorithms
The lecture treats relaxation as the fundamental shortest-path move. You maintain a tentative label D[v] for each vertex and improve it whenever going through some edge gives a better route.
For an edge \((u,z)\), replace D[z] by min(D[z], D[u] + w(u,z)). If the new route is cheaper, update the predecessor of z as well.
Why labels start at infinity
At the start, nothing is known except the source distance 0. Infinity is a clean way to say “no route found yet.”
What relaxation is really testing
Every relaxation asks one question: if the best known route to u is trusted, does extending through \((u,z)\) beat the current best claim for z?
Week 9 is much easier once you stop memorizing algorithm names and start seeing them as different schedules for performing relaxations.
Dijkstra: Greedy Single-Source Shortest Paths with a Priority Queue
Dijkstra's algorithm keeps a set S of vertices whose distances are already final, and repeatedly settles the remaining vertex with the smallest tentative label. After each settlement, it relaxes outgoing edges from that vertex.
Initialize
Set D[s]=0, all other labels to infinity, and place all vertices in a min-priority queue keyed by current distance label.
Remove the minimum label
The next extracted vertex is the current best candidate to become permanently correct.
Relax its outgoing edges
Neighbors may receive improved labels, which trigger priority-queue updates and parent changes.
| Lecture point | Interpretation |
|---|---|
| Setup work is \(O(n)\) | Initialize labels, parents, and the queue. |
| Graph scanning outside PQ work is \(O(m)\) | Across the whole algorithm, adjacency-list edge scans add up linearly in the number of edges. |
| With a heap, runtime is \(O(m \log n)\) | The queue dominates once remove_min and decrease_key are counted. |
| With a Fibonacci heap, runtime improves to \(O(m + n \log n)\) | The lecture is showing how ADT choice sharpens algorithm complexity. |
When Dijkstra extracts the smallest label, it commits to the claim that this distance will never need to decrease later.
That is safe only if future path extensions cannot subtract cost. Non-negative edges guarantee that extending a path cannot make it cheaper than what has already been settled.
A negative edge can violate that monotonicity, which is exactly why the greedy proof fails.
MST Principles: Cheapest Global Connectivity Is Not a Shortest-Path Problem
The second half of the lecture changes the optimization target. A minimum spanning tree does not care about source distances at all. It only cares about selecting a spanning tree whose total edge weight is as small as possible.
| Optimization problem | What it minimizes | What it outputs |
|---|---|---|
| Single-source shortest paths | Distance from one source to each vertex | A shortest-path tree rooted at the source |
| Minimum spanning tree | Total weight of a spanning tree | A globally cheapest connecting tree |
Cut property
For any cut, the cheapest edge crossing it is safe to include in some MST.
Cycle property
Within any cycle, the heaviest edge cannot belong to the MST when edge costs are distinct.
Why both matter
Prim grows an MST by repeatedly using the cut property, while Kruskal often feels like the cycle property in action.
Students often blur Prim and Dijkstra because both use priority queues. The invariant is different: Dijkstra keys vertices by distance from the source, while Prim keys them by cheapest connection into the current tree.
Prim: Grow One Tree Outward Using the Cheapest Crossing Edge
Prim starts from an arbitrary vertex and grows one connected tree. At every step, it adds the lightest edge from the current tree to a vertex outside the tree. The lecture's implementation makes this concrete with an array d[v] and a priority queue.
Pick any start vertex
The start does not change correctness, only the specific MST chosen when ties are possible.
Track cheapest attachment cost
For each outside vertex v, keep d[v] as the cheapest edge from the current tree into v.
Repeatedly attach the best vertex
Delete the minimum d[v], add that vertex to the tree, and update neighbors just as the lecture's table walk-through does.
Most useful comparison sentence: Dijkstra and Prim have strikingly similar code shape, but the label in Dijkstra means “distance from source,” while the label in Prim means “cheapest connecting edge into the current MST.”
Complexity from the lecture
Prim has essentially the same queue analysis shape as Dijkstra: \(O(m \log n)\) with a heap, and \(O(m + n \log n)\) with a Fibonacci heap.
Kruskal & Union-Find: Sort Edges, Then Prevent Cycles Efficiently
Kruskal attacks the MST problem from the opposite direction. Instead of growing one connected tree outward, it scans edges in increasing order of weight and adds an edge whenever doing so does not create a cycle.
| Step | What Kruskal does | Why it is safe |
|---|---|---|
| Sort edges | Process edges from lightest to heaviest. | The cut property tells us cheap safe edges should be taken early. |
| Test for cycle | Add the edge only if its endpoints are currently in different components. | Otherwise it would close a cycle and violate the cycle property. |
| Merge components | After adding a safe edge, union the two components. | This keeps the component partition synchronized with the growing forest. |
Why naive cycle checking is too slow
If you run DFS every time you consider an edge, the main loop becomes expensive. The tutorial quotes \(O(mn)\) for this basic approach.
Why Union-Find helps
Union-Find keeps track of the evolving component partition directly, so cycle tests become component-identity tests rather than fresh graph traversals.
The lecture's simple Union-Find implementation still leaves a nontrivial runtime, but the conceptual gain is the important thing here: MST algorithms often succeed because we find the right auxiliary data structure to represent “which pieces are already connected?”
Tutorial & problem lens: Week 9 is about comparing greedy ideas, not memorizing one algorithm
The tutorial is excellent this week because it forces you to compare algorithms rather than run them mechanically. That is exactly the right preparation for an exam or an interview question, where the main challenge is often choosing the right optimization lens before doing any calculations.
Problems directly tied to the lecture
- Directed-graph Dijkstra: same greedy framework, but relax outgoing directed edges and think in directed paths.
- Compare Kruskal and Prim orderings on the same graph to see that they can build the same MST through different local choices.
- Weight transformations: learn what changes shortest paths, what preserves MSTs, and why the two objectives react differently.
Problem-solving extensions
- Tie-break shortest paths by fewest edges using modified edge lengths.
- Handle vertex costs by re-modeling the path objective carefully.
- Prove correctness of improving-mst and reverse-mst style algorithms.
- Compute all-pairs bottleneck bandwidth in \(O(n^3)\).
- Model library-and-road planning as a graph optimization problem.
Best study habit for Week 9
When you read any graph optimization question, say out loud what the objective function is before naming an algorithm. “Minimize source-to-destination path cost” and “minimize total spanning-tree cost” sound similar, but they lead to fundamentally different greedy invariants.
Quiz Hub & spaced review
Use the inline checks to make sure you can explain relaxation, Dijkstra's key assumption, and the MST objective first. Then use the mixed tools to practice distinguishing shortest paths from spanning trees without being led by the chapter headings.
Recommended sequence. Re-run one small Dijkstra example and one small Prim or Kruskal example by hand, answer the inline checks without notes, and then open the Quiz Hub or flashcards for mixed retrieval.