Едмондс–Карпов алгоритам — разлика између измена

== Алгоритам ==

Алгоритам је идентичан [[Форд-Фулкерсон алгоритам|Форд-Фулкерсон алгоритму]] осим што је дефинисан редослед приликом претраживања. Пронађени пут мора бити најкраћи пут који има расположиве капацитете. То се може постићи [[Претрага у ширину|претрагом у ширину]] када ставимо да гране имају јединичну дужину. Време извршавања <math>O(|V||E|^2)</math> је пронађено показивањем да се свака увећавајућа путања може наћи у времену <math>O(|E|)</math> јер сваки пут најмање једна од ''<math>E</math>'' грана постаје ''засићена'' (грана која има максимални могући проток) и да је дужина највише <math>|V|</math>. Друго својство овог алгоритма је да се дужина најкраће увећавајуће путање увећава монотоно. Доказ се може пронаћи у књизи ''Introduction to Algorithms''.<ref>{{Cite book |last=Cormen|first=Thomas H.|authorlink=Thomas H. Cormen, [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronald L. Rivest]]

 

== Имплементација ==

 

== Литература ==

 

[[Категорија:Проточни граф]]