This work presents the first published algorithm to simultaneously optimize both short- and long-path timing constraints in a Field-Programmable Gate Array (FPGA): the Routing Cost Valleys (RCV) algorithm. RCV consists of two components: a new slack allocation algorithm that determines both a minimum and a maximum delay budget for each circuit connection, and a new router that strives to meet and, if possible, surpass these connection delay constraints. RCV improves both long-path and short-path timing slack significantly versus an earlier Computer-Aided Design (CAD) system, showing the importance of an integrated approach that simultaneously optimizes both types of timing constraints. It is able to meet longpath and short-path timing on all 157 Peripheral Component Interconnect (PCI) cores tested, while an earlier algorithm failed to achieve timing on 75% of the cores. Even in cases where there are no short-path timing constraints, RCV outperforms a stateof- the-art FPGA router and improves the maximum clock speed of circuits by an average of 3.2% (and up to 24.7%).