  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 the physics of interacting polymers and
disordered systems to analyze macroscopic properties of generic
path-optimization problems and derive a simple, principled, generic and
distributed 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.
