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