We discuss how to solve the classical all-pairs-shortest-path problem via simple evolutionary/genetic algorithms. Our rigorous run-time analysis shows that the use of crossover does speed-up the optimization time. This is the first time that such a behaviour is proven for a non-artificial problem.