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)~.