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

У рачунарству '''Едмондс - Карп''' алгоритам је имплементација [[Форд-Фулкерсон алгоритам|Форд-Фулкерсон алгоритмa]] за израчунавање максималног протока у мрежи протока у времену ''[[big O notation|O]]''(''V'' ''E''²). Алгоритам је први пут објавио Yefim (Chaim) Dinic 1970 [[Диницов алгоритам]]<ref>{{cite journal |first=E. A. |last=Dinic |title=Algorithm for solution of a problem of maximum flow in a network with power estimation |journal=Soviet Math. Doklady |volume=11 |issue= |pages=1277–1280 |publisher=Doklady |year=1970 |url= |doi= |id= |accessdate= }}</ref> и самостално су објавили [[Џек Едмондс|Jack Edmonds]] и [[Ричард Карп|Richard Karp]] 1972. године. <ref>{{cite journal |last1=Edmonds |first1=Jack |author1-link=Jack Edmonds |last2=Karp |first2=Richard M. |author2-link=Richard Karp |title=Theoretical improvements in algorithmic efficiency for network flow problems |journal=Journal of the ACM |volume=19 |issue=2 |pages=248–264 |publisher=[[Association for Computing Machinery]]|year=1972 |url= |doi=10.1145/321694.321699 |id= |accessdate= }}</ref> Алгоритам обухвата додатне технике које смањују време извршавања на ''O''(''V''²''E'').

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