CMD + K

Kapittel 12 · Maksimal flyt
maksimal flyt

Ford-Fulkerson: send flyt langs forsterkende stier

1:12Fortellerstemme
0:00 / 0:00

Maksimal flyt fra kilde til sluk i en kapasitert graf. Ford-Fulkerson kjører i runder: så lenge det finnes en sti fra S til T der hver kant har plass igjen, send flyt lik flaskehalsen langs den stien. Vist på fire noder og fem rettede kanter — tre forsterkende stier på rad: S-A-T sender fire enheter og metter A-T, S-B-T sender seks og metter S-B, og til slutt S-A-B-T henter de to siste enhetene ved å snike forbi den mettede A-T-kanten. Total flyt blir tolv.