GPS-SP: Generative Problem Solver for the Shortest Path Problem

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.