Answers are grounded in this paper and cite their sources.
Shows improved efficiency in solving shortest path problems, indicating a new framework for optimization.
Finding shortest paths in graphs with complex constraints is a fundamental problem in optimization with applications ranging from network routing to robotics. Traditional approaches either rely on exhaustive enumeration, which has exponential complexity, or generic constraint solvers that fail to exploit the problem structure. We present a constraint-aware optimization framework Generative Problem Solver for the Shortest Path Problem (GPS-SP) that categorizes constraints by their computational properties and applies specialized algorithms to each category. Our framework enables automatic problem generation and constraint composition, there by forming a generative problem solver for shortest path problems. It supports five constraint categories: (A) hard filters for static graph filtering, (B) regular constraints expressible as finite automata, (C) budget constraints on accumulated resources, (D) global graph properties, and (E) combinatorial constraints. We prove the completeness and optimality of our approach for all category combinations and demonstrate a 14.9× average speedup (54.4× median) over exhaustive search on 1,500 benchmark problems and a 89× average speedup (4,624× median) over GPT-5.2 on 1,280 benchmark problems with 54.2% agreement rate. This work provides both theoretical guarantees and practical efficiency for constraint shortest path problems and demonstrates a blueprint for extending the framework to other combinatorial optimization domains.
No takes yet. Share an insight, caveat, or question.
Lyu et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: