Ce se intampla la primii pasi?
- Se cauta drumuri de lungime minima de la S la D, primele vor fi de cost 0 (practic acele valori X unde avem capacitate si pe S<->X si pe X<->D
- Dupa aceea vor urma drumuri de forma: S -> X -> X+1 -> X+2 -> ... -> Y -> D sau S -> X -> X-1 -> X-2 -> X-3 -> ... -> Y -> D
Observatie:
Daca X si Y sunt alesi la un drum atunci fie
- Y este minim cu proprietatea ca Y > X si muchia Y <-> D inca are capacitate, fie
- Y este maxim cu proprietatea ca Y < X si muchia Y <-> D inca are capacitate
Analog pentru X fata de Y.
Daca nu se intampla una din cele 2 putem obtine un alt drum la fel de bun dar cu proprietatea dorita.
