  Shortest-path games are two-player zero-sum games played on a graph equipped
with integer weights. One player, that we call Min, wants to reach a target set
of states while minimising the total weight, and the other one has an
antagonistic objective. This combination of a qualitative reachability
objective and a quantitative total-payoff objective is one of the simplest
setting where Min needs memory (pseudo-polynomial in the weights) to play
optimally. In this article, we aim at studying a tradeoff allowing Min to play
at random, but using no memory. We show that Min can achieve the same optimal
value in both cases. In particular, we compute a randomised memoryless
$\varepsilon$-optimal strategy when it exists, where probabilities are
parametrised by $\varepsilon$. We then characterise, and decide in polynomial
time, the class of games admitting an optimal randomised memoryless strategy.
