Форд-Фулкерсонов алгоритам
From Wikipedia, the free encyclopedia
Форд-Фулкерсон метод (назван по Л. Р. Форду, мл. и Д. Р. Фулкерсону је алгоритам који рачуна максимални проток у транспортној мрежи. Објављен је 1956. Име "Форд-Фулкерсон" се често користи и за Едмондс-Карп алгоритам, који је специјализација Форд-Фулкерсона.
Основна идеја је једноставна. Докле год постоји путања од извора (почетни чвор) до понора (крајњи чвор), са доступним капацитетима на свим гранама путање, слаћемо проток дуж једне од ових путања. Тада проналазимо нову путању итд. Путања се доступним капацитетом се назива појачавајућа путања.