Problem. There are n cities and flights (from, to, price). Return the cheapest price from src to dst with at most k
stops (so at most k + 1 flights), or −1 if no such route exists.
flights = [(0, 1, 100), (1, 2, 100), (2, 3, 100), (0, 3, 500)], src = 0, dst = 3
k = 1 → 500 (0 → 3 directly; 0 → 1 → 2 → 3 needs 2 stops)
k = 2 → 300
Lesson 11.10's Dijkstra finds the cheapest route, but ignores the number of edges. With a hop limit, the cheapest route may be too long, and the best allowed route may be one that Dijkstra discarded because it was more expensive at an intermediate city. The fix is to make the hop count part of the problem.
ML context. Constrained routing shows up when requests pass through a chain of models or services with a cap on calls: an agent allowed at most k tool calls, a cascade that may escalate at most k times to bigger models, a data-format conversion graph where each hop loses some precision so only short chains are acceptable. "Cheapest with at most k edges" is the core query in each (Change D).