  The all-pairs shortest path problem is the first non-artificial problem for
which it was shown that adding crossover can significantly speed up a
mutation-only evolutionary algorithm. Recently, the analysis of this algorithm
was refined and it was shown to have an expected optimization time (w.r.t. the
number of fitness evaluations) of $\Theta(n^{3.25}(\log n)^{0.25})$.
  In contrast to this simple algorithm, evolutionary algorithms used in
practice usually employ refined recombination strategies in order to avoid the
creation of infeasible offspring. We study extensions of the basic algorithm by
two such concepts which are central in recombination, namely \emph{repair
mechanisms} and \emph{parent selection}. We show that repairing infeasible
offspring leads to an improved expected optimization time of
$\mathord{O}(n^{3.2}(\log n)^{0.2})$. As a second part of our study we prove
that choosing parents that guarantee feasible offspring results in an even
better optimization time of $\mathord{O}(n^{3}\log n)$.
  Both results show that already simple adjustments of the recombination
operator can asymptotically improve the runtime of evolutionary algorithms.
