This paper presents the Routing Cost Valleys (RCV) algorithm -- the first published algorithm that simultaneously optimizes all short- and long-path timing constraints in a Field-Programmable Gate Array (FPGA). RCV is comprised of a new slack allocation algorithm that produces both minimum and maximum delay budgets for each circuit connection, and a new router that strives to meet and, if possible, surpass these connection delay constraints. RCV achieves excellent results. On a set of 100 large circuits, RCV improves both long-path and short-path timing slack significantly vs. an earlier Computer-Aided Design (CAD) system that focuses solely on long-path timing. Even with no short-path timing constraints, RCV improves the clock speed of circuits by 3.9% on average. Finally, RCV is able to meet timing on all 72 Peripheral Component Interconnect (PCI) cores tested, while an earlier algorithm fails to achieve timing on all 72 cores.