When the Shortest Path Isn't Obvious
Students are solving a discrete-math routing problem: a delivery driver must visit four locations A, B, C, D starting and ending at the depot, and the class is comparing routes. Distances (in minutes): Depot–A 4, Depot–B 7, Depot–C 6, Depot–D 5, A–B 3, A–C 8, A–D 6, B–C 2, B–D 9, C–D 4. A student proposes Depot → A → B → C → D → Depot and claims it is optimal because "each leg is short." A second student proposes Depot → B → C → A → D → Depot. The teacher wants students to reason about why a greedy "short legs" strategy can fail and to justify optimality rather than assert it.
1. Compute the total time for both proposed routes and determine which is shorter. Then explain why choosing individually short legs does not guarantee the shortest tour.
Read the worked answer
Route 1 (Depot→A→B→C→D→Depot): 4 + 3 + 2 + 4 + 5 = 18 minutes. Route 2 (Depot→B→C→A→D→Depot): 7 + 2 + 8 + 6 + 5 = 28 minutes.
Route 1 is shorter (18 vs 28). However, the reason it is shorter is not that each leg was chosen greedily - it is that the tour as a whole uses the cheap edges A–B (3), B–C (2), C–D (4) and returns via the short Depot–A (4). The second route is forced to use the expensive A–C (8) and A–D (6).
The lesson: a tour is a cycle that must use each location exactly once, so local choices interact globally. Choosing the shortest edge out of each node (greedy) can strand you with expensive edges later, because every location must be entered and left exactly once. Optimality requires comparing complete tours, not summing locally short legs.
2. Describe a systematic method students could use to be confident Route 1 is optimal (or to find a better route), and explain the role of a lower bound in that argument.
Read the worked answer
Students can enumerate tours systematically by fixing the depot and listing the 3! = 6 orderings of A, B, C, D (since the tour is a cycle, fix one direction to avoid double-counting). Computing all six totals and comparing gives certainty for this small instance.
A lower bound supports the argument without full enumeration: for any tour, each location must be entered and left, so the tour uses two edges at each of the four locations. A valid lower bound can be built by, at each location, taking the two cheapest incident edges and summing, then halving (since each edge is counted at both ends). For example, at B the two cheapest edges are B–C (2) and A–B (3) = 5; summing such minima across locations and dividing by 2 gives a bound no tour can beat. If Route 1's total equals or nearly meets this bound, students have strong evidence of optimality. The bound also explains why: any tour must pay at least the cheapest possible connections at every stop, so if a route achieves that, it cannot be improved.