nave-bunicu-hint2

Hint 2

Scrie aici despre nave-bunicu-hint2

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 &gt; X$ si muchia $Y <-> D$ inca are capacitate, fie
* $Y$ este maxim cu proprietatea ca $Y &lt; 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.