Key Idea: Route algorithms find the cheapest way through a network. Some connect every vertex, one finds the shortest path between two vertices, and others plan a tour along every edge or through every vertex.
| Job | Algorithm |
|---|---|
| Connect all vertices cheaply (n − 1 edges, no cycle) | Minimum spanning tree |
| Sort edges cheap to dear, skip any that makes a cycle | Kruskal's |
| Grow one tree from a start vertex | Prim's |
| Shortest route between two vertices | Dijkstra's |
Dijkstra's algorithm
- Label — Give each vertex a temporary label: the best distance so far.
- Fix — Make the smallest temporary label permanent.
- Update — A neighbour's label becomes the smaller of its old label and (this permanent value + the edge).
- Finish — Repeat until the target is permanent, then trace the route back.
Route inspection and travelling salesman
- Route inspection: the shortest closed walk along all edges. Add the cheapest pairing of odd-degree vertices to the edge total.
- Travelling salesman: the shortest closed route through all vertices.
- Upper bound: nearest neighbour, which is a real route.
- Lower bound: delete a vertex, find the MST of the rest, and add back the two cheapest edges at the deleted vertex.
Postman covers every edge; salesman visits every vertex.
Delete A: the MST of the rest is 59, and A's two cheapest edges are 20 and 28. Lower bound? 59 + 48 = 107.
A gritting lorry must drive down every road. Which problem is this? Route inspection.
In Kruskal's, the next cheapest edge closes a cycle. What do you do? Skip it and move on.
In Dijkstra's, C = 2 is permanent, edge C–B = 1, and B's label is 4. New label for B? min(4, 2 + 1) = 3.