Optimizing paths on networks is crucial for many applications, from subway traffic to Internet communication. As global path optimization that takes account of all path-choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing sub-optimal solutions. We employ thephysics of interacting polymers and disordered systems to analyzemacroscopic properties of generic path-optimization problems andderive a simple, principled, generic and distributive routing algorithm capable of considering simultaneously all individual path choices. We demonstrate the efficacy of the new algorithm by applying it to: (i) random graphs resembling Internet overlay networks; (ii)travel on the London underground network based on Oyster-card data; and (iii) the global airport network. Analytically derived macroscopic properties give rise to insightful new routing phenomena, including phase transitions and scaling laws, which facilitate better understanding of the appropriate operational regimes and their limitations that are difficult to obtain otherwise.