Pour cela, on va remplacer chaque ville $A$ par $K+1$ villes $A_0$, $A_1$, …, $A_K$ correspondant à la ville $A$ aux instants 0, 1, …, $K$.

$\,$

Il faut aussi adapter les arcs. Indication