The shortest path problem with resource constraints (SPPRC) is often used as a subproblem within a column generation approach for routing and scheduling problems. It aims to find a least cost path between the source and the destination nodes in a network while satisfying the resource consumption limitations on every node. The SPPRC is usually solved using dynamic programming. Such approaches are effective in practice, but they can be inefficient when the network is large and especially when the number of resources is high. To cope with this major drawback, we propose a new exact primal algorithm that explores the solution space iteratively using a path-adjacency-based partition. Numerical experiments for vehicle and crew scheduling instances demonstrate that the new approach outperforms both the standard dynamic programming and the multi-directional dynamic programming methods.