Abstract: In order to solve the problems of key waste and low transmission efficiency in the existing routing scheme of quantum key distribution (QKD) network based on trust relay, a random routing algorithm based on backtracking is proposed to improve the existing routing algorithm. In the process of routing, the algorithm adds backtracking points to each branch, in the transmission process along the selected path, when the key quantity of a certain link is insufficient, by looking for the nearest backtracking point, the key can be transferred along the randomly selected new path again from the backtracking point. The comparison experiment and analysis results show that the algorithm has certain advantages in routing time, key consumption and key transmission efficiency.