À un arc $u$ de longueur $l_u$, on associe un arc identique, de coût $l_u$, de capacité minimale 0 & maximale $\infty$.

On rajoute un arc $(y,x)$ de capacité minimale 1, maximale $\infty$ & de coût nul.