Napravićemo novi usmeren graf sa $2N$ čvorova, gde svaki čvor predstavlja uređen par $(u,p)$, gde je $u$ čvor originalnog grafa, a $p$ vrednost $0$ ako je prethodni čvor bio različite boje, ili $1$ ako je bio iste boje. Ovaj graf konstrujišemo od početnog na sledeći način: ako su dva čvora $u$ i $v$ iste boje povezane granom, tada u novom grafu dodamo granu od $(u,0)$ ka $(v,1)$ i od $(v,0)$ ka $(u,1)$ (što predstavlja da ukoliko smo došli iz istobojnog čvora, sada moramo da drugi parametar bude $1$); a ako su čvorovi $u$ i $v$ povezane granom, onda dodamo granu između parova čvorova ($(u,0)$ ka $(v,0)$), ($(u,1)$ ka $(v,0)$), ($(v,0)$ ka $(u,0)$) i ($(v,1)$ ka $(u,0)$) (što predstavljava da smo se vratili u stanje $0$, jer prethodni nije iste boje).

Kada napravimo ovaj graf, na njemu pustimo običnu pretragu po širini, i rešenje nam je najkraće od rastojanja do $(N,0)$ i $(N,1)$. Vremenska složenost ovog algoritma je $O(N+M)$.