Tier 7 Capstone: Routing a Delivery

A real delivery-routing system rarely gets asked just one kind of question. Sometimes it needs the single cheapest way to get from a warehouse to one specific address. Other times it needs a completely different answer: given a fixed budget, which of the surrounding delivery stops can be reached at all? Both questions are built on the same underlying graph and the same shortest-path machinery from the last two chapters. They just ask different things of it, which is exactly what this tier's capstone, RouteOptimizer, asks you to build.

shortest_route(start, end) is the question Dijkstra was built for in the last module, with one addition: reporting distance alone is not enough for a delivery system. It needs the actual sequence of stops. That requires tracking, for every node, which node it was most recently reached from (its "predecessor" on the current-best path), then walking that chain of predecessors backward from end to start once Dijkstra finishes, and reversing it into a forward route.

cheapest_stops_under_budget(start, budget) asks something different: not "how do I reach one destination as cheaply as possible," but "of everywhere reachable, which stops cost no more than my budget to reach?" The shortest-path distances Dijkstra computes from start answer that directly. Run Dijkstra once from start, and every node whose resulting distance is within budget is part of the answer. The same core routine (relax edges via a min-heap, always expand the cheapest known node next) answers both questions. The only difference is what happens with the distances afterward.

Look back across this entire tier and a pattern emerges: real systems rarely need just one algorithmic idea in isolation. Backtracking's systematic search, dynamic programming's reuse of overlapping subproblems, greedy's bet on locally-best choices, and graph traversal's way of modeling networks of relationships all show up together in practice. A routing system leans on shortest paths (graphs), a scheduling system leans on interval selection (greedy), and plenty of optimization problems underneath both still reduce to a DP table when the greedy-choice property does not hold. RouteOptimizer is a small, concrete example of exactly that: one graph, one core shortest-path routine, reused twice with two different questions asked of its results.

• -shortest_route reuses Dijkstra plus a predecessor map, walked backward from the destination to reconstruct the actual path, not just its cost.
• -cheapest_stops_under_budget reuses the exact same Dijkstra core, but reads the entire distances table afterward instead of just one entry, filtering by budget rather than by destination.
• -This is the pattern to carry forward past this course: most "new" problems are a familiar core algorithm (a traversal, a DP table, a greedy pass) combined with a different question asked of its output.