Trees and paths¶
Part 2 of the course, volume 2 of the lecture notes: chapters 2–3.
Minimum spanning trees (Kruskal, Prim, the cut and cycle properties) and shortest paths (acyclic graphs, Bellman–Ford, Dijkstra), with potentials as a certificate of optimality.
Lecture notes (PDF) Exercises (PDF)
-
2. Minimum spanning trees
The minimum spanning tree problem · Cuts and cycles · The cut property and the cycle property · The generic greedy algorithm
-
3. Shortest paths
Shortest path problems · Optimality conditions and potentials · The linear programming formulation · Shortest paths in acyclic graphs