Constrained Shortest Path

Problem Implement a shortest-path algorithm over a weighted graph subject to an additional constraint — for example a hard limit on the number of edges/stops used, or a second cost dimension such as a fuel or time budget that must not be exceeded. A classical shortest-path algorithm must be modified rather than applied directly.

Input / Output

• Input: a graph as an adjacency list with edge weights, a source src, a destination dst, and a constraint budget K (e.g. at most K stops).
• Output: the minimum total cost from src to dst respecting the constraint, or -1 if unreachable within it.

Constraints

• Up to ~10^5 nodes and edges; K is typically small relative to n.
• Edge weights are non-negative for the Dijkstra variant; Bellman–Ford handles negative weights (but no negative cycles).
• The constraint is additive along the path.

Example

• Four cities with flights 0->1 cost 100, 1->2 cost 100, 0->2 cost 500. From 0 to 2 with at most 1 stop → 200 via 0->1->2. With 0 stops allowed → 500, the direct flight.
• Tricky case: the globally cheapest path may violate the constraint, so the answer is not simply "run Dijkstra and check". A node may need to be visited several times at different constraint levels.