Едмондс–Карпов алгоритам — разлика између измена
Садржај обрисан Садржај додат
м razne ispravke |
м ciscenje dupliranih poziva |
||
Ред 4:
== Алгоритам ==
Алгоритам је идентичан [[Форд-Фулкерсон алгоритам|Форд-Фулкерсон алгоритму]] осим што је поредак при претраживању дефинисан. Пронађени пут мора бити најкраћи пут који има расположиве капацитете. То се може постићи претрагом у ширину када допустимо да гране имају јединичну дужину. Време извршавања ''O''(''V'' ''E''<sup>2</sup>) је пронађено показивањем да се свака увећавајућа путања може наћи у времену ''O''(''E'') јер сваки пут најмање једна од ''E'' грана постаје ''засићена'' (грана која има максимални могући проток) и да је дужина највише ''V''. Друго својство овог алгоритма је да се дужина најкраће увећавајуће путање увећава монотоно. Доказ се може погледати у ''Introduction to Algorithms''.<ref>{{Cite book |last=Cormen|first=Thomas H.|authorlink=Thomas H. Cormen, [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronald L. Rivest]]
and [[Clifford Stein]] |title=[[Introduction to Algorithms]] |publisher=MIT Press |year=2009 |isbn=978-0-262-03384-8 |edition=third |chapter=26.2 |pages=727–730}}</ref>
== Имплементација ==
Линија 318 ⟶ 317:
== Литература ==
* {{Cite book |last=Cormen|first=Thomas H.|authorlink=Thomas H. Cormen, [[Charles E. Leiserson]], [[Роналд Лин Ривест|Ronald L. Rivest]]
and [[Clifford Stein]] |title=[[Introduction to Algorithms]] |publisher=MIT Press |year=2009 |isbn=978-0-262-03384-8 |edition=third |chapter=26.2 |pages=727–730}}
[[Категорија:Проточни граф]]
| |||