Constrained Shortest Path, in depth: why one budget makes it NP-hard, resource DP, label setting with dominance and LARAC

The problem and why it is hard

Take a directed graph where each edge e has a cost c(e) and a resource use r(e), both non-negative. Given a source s, a target t and a budget T, find a path P from s to t that minimizes the sum of c(e) over P subject to the sum of r(e) over P being at most T. With one resource this is the weight-constrained shortest path; with several (time, fuel, toll count) it is the general RCSP.

The problem is NP-hard, even with a single resource. The reduction is from knapsack: build a chain of nodes where, at each step, one parallel edge means take item i (cost 0, resource equal to its weight) and the other means skip it (cost equal to its value, resource 0). The cheapest path under the weight budget leaves behind the least value, so it is an optimal knapsack packing. If you know the knapsack problem, you already know the shape of the difficulty: it is NP-hard in general but solvable in time proportional to the budget when resources are small integers. RCSP inherits both facts.

Why Dijkstra alone fails

Dijkstra works because of optimal substructure on a single number: once you know the cheapest way to reach node v, every cheapest path through v starts with it, so you can finalize v and discard the rest. With a constraint, the cheapest way to v may use too much resource to finish the trip, while a more expensive way that uses less resource is the one that completes. You cannot keep one value per node.

In the example with a budget of 7, the cheapest way to reach b is s-a-b at cost 2 and time 7. It fits the budget, so one-label Dijkstra keeps it and throws away s-b at cost 4 and time 2. But s-a-b has no time left to go anywhere, and the discarded s-b is the start of the only feasible route, s-b-c-t at cost 8. One-label Dijkstra reports no path at all. At budget 12 it keeps s-a-c (cost 2, time 11), cannot finish, and settles for s-a-t at cost 7 when s-a-b-c-t costs 6. A node therefore needs a set of partial paths, and the whole art is keeping that set small.

Dynamic programming over the resource

If resources are small non-negative integers, define best(v, r) as the minimum cost to reach v using at most r units of resource. Then best(s, r) is 0 for every r, and for each edge (u, v) with resource ru, best(v, r) can be best(u, r minus ru) plus the edge cost. Filling the table for r from 0 to T gives the answer at best(t, T) in O(T times |E|) time. That is pseudo-polynomial: fast when T is in the hundreds or thousands, useless when resources are milliseconds over a long horizon or real numbers.

def rcsp_dp(edges, nodes, source, target, budget):
    """edges: (u, v, cost, res) with integer res >= 1. Answer for res <= budget."""
    INF = float("inf")
    dp = {(v, r): INF for v in nodes for r in range(budget + 1)}
    for r in range(budget + 1):
        dp[(source, r)] = 0
    for r in range(budget + 1):          # increasing r: dp[u, r - res] is final
        for u, v, cost, res in edges:
            if res <= r and dp[(u, r - res)] + cost < dp[(v, r)]:
                dp[(v, r)] = dp[(u, r - res)] + cost
    return dp[(target, budget)]

The loop order matters: because every edge uses at least one unit, entries at resource r depend only on entries at smaller r, which are final. Edges with zero resource break that argument; handle them with a Dijkstra pass on cost within each r layer. The classic fully polynomial approximation scheme (Hassin, 1992) uses the mirror image of this DP: it indexes by rounded cost and keeps the resource budget strict. Rounding resources instead gives a bicriteria variant that may exceed the budget slightly.

Label setting with dominance and bounds

The exact method used in practice is label setting. A label is a partial path summarized by (cost, resource) at its end node. Label A dominates label B at the same node if A has no more cost and no more resource: any completion of B is also a completion of A, at least as good. Dominated labels are discarded, so each node keeps a Pareto front. Two lower bounds, computed once by running Dijkstra backwards from t on cost and on resource, add powerful pruning: a label whose resource plus the minimum resource still needed exceeds T can never finish, and a label whose cost plus the minimum remaining cost is no better than the best complete path found cannot win.

import heapq
from collections import defaultdict

def rcsp_labels(edges, source, target, budget):
    adj, radj = defaultdict(list), defaultdict(list)
    for u, v, cost, res in edges:
        adj[u].append((v, cost, res))
        radj[v].append((u, cost, res))
    min_cost = reverse_dijkstra(radj, target, 0)   # lower bound on cost to target
    min_res = reverse_dijkstra(radj, target, 1)    # lower bound on resource to target
    if min_res[source] > budget:
        return None
    front = defaultdict(list)          # node -> non-dominated (cost, res) labels
    best, best_path = float("inf"), None
    pq = [(min_cost[source], 0, 0, source, (source,))]
    while pq:
        bound, cost, res, v, path = heapq.heappop(pq)
        if bound >= best:
            break                      # ordered by bound: nothing better remains
        if v == target:
            best, best_path = cost, path
            continue
        for w, c, r in adj[v]:
            nc, nr = cost + c, res + r
            if nr + min_res[w] > budget or nc + min_cost[w] >= best:
                continue               # cannot finish, or cannot beat incumbent
            if any(fc <= nc and fr <= nr for fc, fr in front[w]):
                continue               # dominated at w
            front[w] = [(fc, fr) for fc, fr in front[w] if not (nc <= fc and nr <= fr)]
            front[w].append((nc, nr))
            heapq.heappush(pq, (nc + min_cost[w], nc, nr, w, path + (w,)))
    return best, best_path

The queue is ordered by cost plus the admissible cost bound, which is A-star on the cost dimension; the A-star article explains why an admissible bound keeps the first complete path optimal. The reverse_dijkstra helper is plain Dijkstra on reversed edges using one weight component, as in the Dijkstra deep dive. Storing full path tuples is fine for teaching; production code stores a parent pointer per label.

LARAC: Lagrangian relaxation

When exactness is too expensive, Lagrangian relaxation moves the constraint into the objective. For a multiplier lambda of zero or more, find the path minimizing cost plus lambda times resource with ordinary Dijkstra. Lambda zero gives the cheapest path; a huge lambda gives the least-resource path. LARAC (Lagrangian Relaxation Aggregated Cost) keeps two paths, pc (cheap but infeasible) and pr (feasible but expensive), sets lambda so both have equal aggregated cost, and runs Dijkstra with that lambda. A feasible result replaces pr, an infeasible one replaces pc, and it stops when the new path ties the old ones.

def larac(edges, source, target, budget):
    pc = dijkstra_path(edges, source, target, lambda c, r: c)      # (cost, res, path)
    if pc[1] <= budget:
        return pc
    pr = dijkstra_path(edges, source, target, lambda c, r: r)
    if pr[1] > budget:
        return None                                                # infeasible
    while True:
        lam = (pc[0] - pr[0]) / (pr[1] - pc[1])
        q = dijkstra_path(edges, source, target, lambda c, r: c + lam * r)
        if abs((q[0] + lam * q[1]) - (pc[0] + lam * pc[1])) < 1e-9:
            return pr                                              # feasible answer
        if q[1] <= budget:
            pr = q
        else:
            pc = q

Here dijkstra_path is ordinary Dijkstra under the given scalar weight function, returning the path's (cost, resource, path). Each iteration is one Dijkstra, so LARAC is fast and returns a feasible path plus a lower bound on the optimum. It only finds paths on the lower convex hull of the cost-resource trade-off, so it can miss the true optimum, as the example shows.

Worked example

Run all three methods on the graph in the figure. The unconstrained cheapest path is s-a-c-t with cost 3 and time 14. The table shows what happens as the budget tightens; the label and DP columns agree everywhere, and the label column also reports how many queue pops the search took, counted by adding a counter to the loop.

The budget 12 row is the lesson. The optimum s-a-b-c-t (cost 6, time 12) lies above the line joining s-a-c-t (3, 14) and s-a-t (7, 8) in the cost-time plane, so no single lambda makes it the Dijkstra winner. LARAC returns s-a-t at cost 7, a 17 percent gap. Its lower bound, cost 3 plus 0.667 times the overshoot of 2, is about 4.33, which tells you the gap might exist even before you find the optimum. That bound is how branch-and-bound solvers close the gap: they use LARAC bounds to prune, then search exactly inside the remaining window.

Scaling up

On road networks with millions of nodes the label sets, not Dijkstra, become the cost. Practical measures, in order of payoff: compute both reverse bounds first and prune on them, since they often remove most labels; keep fronts sorted by resource so the dominance test is a binary search instead of a linear scan; cap total labels and fall back to LARAC with a reported gap when the cap is hit; and for several resources, accept that fronts grow quickly with dimension and prefer Lagrangian bounds on the extra resources.

Negative costs are allowed only without negative cycles, and then the reverse Dijkstra bounds must become Bellman-Ford style bounds; see SPFA for that. Resources must be non-negative; a recharging resource, as in electric vehicle routing, needs a modified label model with a capacity cap.

Failure modes

• Keeping one label per node. Plain Dijkstra with a feasibility check silently returns suboptimal or no paths. The example breaks it at budgets 12 and 7.
• Label explosion. Fronts grow without bound on large graphs with weakly correlated cost and resource. Add bounds, sort fronts, and set a label cap with a fallback.
• Treating LARAC as exact. It returns hull paths only. Report its gap, or verify with an exact method on a sample.
• Floating-point dominance. Labels that differ only by rounding are kept as distinct. Compare with a tolerance or use integers.
• DP over a fine grid. Millisecond resources over an hour give a table with millions of layers. Coarsen the grid and report the rounding error.

Trade-offs

What to do next

1. Write down your cost, your resource and the budget; check that resources are non-negative and decide integer or real.
2. Implement reverse Dijkstra bounds and test pruning alone on your graph.
3. Implement label setting and compare it against the DP on small random graphs until they always agree.
4. Add LARAC, record its gap against the exact method, and decide whether that gap is acceptable.
5. Measure label counts on production-size inputs and set a cap with a logged fallback.