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.