Algoritmus
A feladat átfogalmazható a maximális folyam problémára. Az irányított élek kapacitása
legyen egységnyi. A két célpontból vezessen egy-egy irányított él egy "nyelő" csúcsba.
A "forrás" legyen az eredeti 1-es pont. Ha tudunk 2 értékű folyamot csinálni, akkor van
két éldiszjunkt út 1-ből a célpontokba.
Mivel az eredeti feladatban csúcsdiszjunkt utakat kell keresni, még egy kicsit átalakítjuk a gráfot: Minden csúcsot (a forrás és a nyelő kivételével) megduplázunk, egy "BE" és egy "KI"
címkéjű csúcs lesz belőle. Az eredeti élek mindig a "KI" és a "BE" csúcsok között haladnak,
és felveszünk minden csúcs "BE" és "KI" példánya között egy-egy irányított élet.
Az így átalakított gráfon lefuttatjuk az Edmonds-Karp-féle folyamalgoritmus első két lépését (első út, és egy javító-út), majd a kapott folyamnak megfelelő utakat adjuk meg
csúcsdiszjunkt útként.
Kód
