Едмондс–Карпов алгоритам — разлика између измена
Садржај обрисан Садржај додат
м Бот: исправљена преусмерења |
м Разне исправке |
||
Ред 1:
{{loš seminarski}}
У рачунарству '''Едмондс - Карп''' алгоритам је имплементација [[Форд-Фулкерсон алгоритам|Форд-Фулкерсон алгоритма]] за израчунавање максималног протока у мрежи протока у времену ''[[Велико О|O]]''(''V'' ''E''<sup>2</sup>). Алгоритам је први пут објавио 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= |publisher=Doklady |year=1970|url= |doi= |id= |accessdate= |pages=1277–1280}}</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 |publisher=[[Association for Computing Machinery]]|year=1972|url= |doi=10.1145/321694.321699 |id= |accessdate= |pages=248–264
== Алгоритам ==
Алгоритам је идентичан [[Форд-Фулкерсон алгоритам|Форд-Фулкерсон алгоритму]] осим што је поредак при претраживању дефинисан. Пронађени пут мора бити најкраћи пут који има расположиве капацитете. То се може постићи претрагом у ширину када допустимо да гране имају јединичну дужину. Време извршавања ''O''(''V'' ''E''<sup>2</sup>) је пронађено показивањем да се свака увећавајућа путања може наћи у времену ''O''(''E'') јер сваки пут најмање једна од ''E'' грана постаје ''засићена'' (грана која има максимални могући проток) и да је дужина највише ''V''. Друго својство овог алгоритма је да се дужина најкраће увећавајуће путање увећава монотоно. Доказ се може погледати у ''Introduction to Algorithms''.<ref>{{Cite book |author=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronald L. Rivest]]
and [[Clifford Stein]] |title=[[Introduction to Algorithms]] |publisher=MIT Press |year=2009
|
== Имплементација ==
Ред 319:
* {{Cite book |author=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronald L. Rivest]]
and [[Clifford Stein]] |title=[[Introduction to Algorithms]] |publisher=MIT Press |year=2009
|
[[Категорија:Проточни граф]]
| |||