constrainedpath

Constrainedpath refers to a class of path-finding problems in graphs where the objective is to minimize a primary measure while satisfying one or more constraints on additional resources. The term is commonly used interchangeably with constrained shortest path problems and resource-constrained shortest path problems.

In the standard formulation, an edge set E of a directed graph G = (V, E) carries a primary cost c(e) and a secondary resource consumption r(e). A budget B specifies the allowable total resource along a path. The goal is to find a path from a designated source s to a destination t that minimizes the total cost while ensuring that the sum of resource consumptions along the path does not exceed B. Variants may impose multiple resource constraints or optimize a secondary criterion subject to these budgets. In many practical settings, there is no single best path; rather, a set of efficient or Pareto-optimal paths may exist.

The constrainedpath problem is typically NP-hard in general, and exact solutions may be computationally intense for large graphs. Several algorithmic approaches address it, including dynamic programming that tracks costs for each possible resource level (pseudo-polynomial time), label-setting and label-correcting methods that maintain a frontier of feasible paths, and exact or heuristic methods based on Lagrangian relaxation or A* search with resource constraints. For problems with two or more constraints, the complexity grows and specialized techniques are often employed.

Applications include transportation and logistics planning with fuel or time budgets, energy-aware routing for battery-powered vehicles or networks, and robotic or autonomous navigation where safety, time, or power imposes limits. Related concepts include multi-criteria shortest path and Pareto-optimal path sets, which handle trade-offs among multiple objectives without aggregating them into a single budget.