www.wikidata.uk-ua.nina.az

Алгоритм Едмондса Карпа розв язує задачу знаходження максимального потоку в транспортній мережі Алгоритм являє собою окр

Алгоритм Едмондса — Карпа

Алгоритм Едмондса — Карпа розв'язує задачу знаходження максимального потоку в транспортній мережі. Алгоритм являє собою окремий випадок методу Форда-Фалкерсона і працює за час . Вперше був опублікований в 1970 році радянським вченим Ю. А. Деніцом. Пізніше, в 1972 році, був незалежно відкритий Едмондсом і Карпом. Алгоритм Дініца подає додаткові підходи для зменшення часу до .

Алгоритм ред.

Алгоритм Едмондса-Карпа — це варіант алгоритму Форда-Фалкерсона, при якому на кожному кроці вибирають найкоротший доповнювальний шлях з в залишкової мережі (вважаючи, що кожне ребро має одиничну довжину). Найкоротший шлях знаходимо пошуком в ширину.

Опис ред.

  • Обнуляємо всі потоки. Залишкова мережа спочатку збігається з початковою мережею.
  • У залишковій мережі знаходимо найкоротший шлях з джерела в стік. Якщо такого шляху немає, зупиняємося.
  • Пускаємо через знайдений шлях (він називається збільшувальним шляхом або збільшувальним ланцюгом) максимально можливий потік:
    • На знайденому шляху в залишковій мережі шукаємо ребро з мінімальною пропускною здатністю
    • Для кожного ребра на знайденому шляху збільшуємо потік на , а в протилежному йому — зменшуємо на
    • Модифікуємо залишкову мережу. Для всіх ребер на знайденому шляху, а також для протилежних їм ребер, обчислюємо нову пропускну здатність. Якщо вона стала ненульовою, додаємо ребро до залишкової мережі, а якщо обнулилась, стираємо його.
  • Повертаємося на крок 2.

Щоб знайти найкоротший шлях в графі, використовуємо пошук в ширину:

  • Створюємо чергу вершин О. Спочатку О складається з єдиної вершини s.
  • Відмічаємо вершину s як відвідану, без предка, а всі інші як невідвідані.
  • Поки черга непорожня, виконуємо наступні кроки:
    • Видаляємо першу в черзі вершину u.
    • Для всіх ребер (u, v), що виходять з вершини u, таких що вершина v ще не відвідана, виконуємо наступні кроки:
      • Відзначаємо вершину v як відвідану, з предком u.
      • Додаємо вершину v в кінець черги.
      • Якщо v=t, виходимо з обох циклів: ми знайшли найкоротший шлях.
  • Якщо чергу порожня, повертаємо відповідь, що шляху немає взагалі і зупиняємося.
  • Якщо ні, йдемо від t до s, щоразу переходячи до предка. Повертаємо шлях у зворотному порядку.

Псевдокод ред. 

algorithm EdmondsKarp input: C[1..n, 1..n] (Ємність матриці) E[1..n, 1..?] (Сусідні листи) s (Джерело) t (Стік) output: f (Значення максимальної витрати) F (Матриця дає правової потік з максимальним значенням) f := 0 (Початковий потік дорівнює нулю) F := array(1..n, 1..n) (Залишкова ємність від u до v це C[u,v] - F[u,v]) forever m, P := BreadthFirstSearch(C, E, s, t, F) if m = 0 break f := f + m (Поверніться до пошуку, і записати потік) v := t while v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u return (f, F) 
algorithm BreadthFirstSearch input: C, E, s, t, F output: M[t] (Знайшли ємність шляху) P (Батьківська таблиця) P := array(1..n) for u in 1..n P[u] := -1 P[s] := -2 (Переконайтеся, що джерело не виявлено) M := array(1..n) (Потужність знайденого шляху до вузла) M[s] := ∞ Q := queue() Q.offer(s) while Q.size() > 0 u := Q.poll() for v in E[u] (Якщо є вільна ємність та v не зустрічався у пошуку) if C[u,v] - F[u,v] > 0 and P[v] = -1 P[v] := u M[v] := min(M[u], C[u,v] - F[u,v]) if v ≠ t Q.offer(v) else return M[t], P return 0, P 


algorithm EdmondsKarp input: graph (Графік списку суміжності вузлів з продуктивністю, потік, зворотній і напрямлений) s (Джерело) t (Стік) output: flow (Максимальне значення потоку) flow := 0 (Початковий потік дорівнює нулю) q := array(1..n) (Ініціалізація q, як графу довжину) while true qt := 0 (Змінна для проходу по всіх відповідним ребрам) q[qt++] := s (Ініціалізація початкового масиву) pred := array(q.length) (Ініціалізація попереднього списку з графом довжини) for qh=0;qh < qt && pred[t] == null cur := q[qh] for (graph[cur]) (Прохід по всім ребрам) Edge[] e := graph[cur] (Кожне ребро має бути пов'язане з ємністю) if pred[e.t] == null && e.cap > e.f pred[e.t] := e q[qt++] : = e.t if pred[t] == null break int df := MAX VALUE (Ініціалізація до максимального значення) for u = t; u != s; u = pred[u].s df := min(df, pred[u].cap - pred[u].f) for u = t; u != s; u = pred[u].s pred[u].f  := pred[u].f + df pEdge := array(PredEdge) pEdge := graph[pred[u].t] pEdge[pred[u].rev].f := pEdge[pred[u].rev].f - df; flow := flow + df return flow

Складність ред.

У процесі роботи алгоритм Едмондса — Карпа буде знаходити кожен доповнюючий шлях за час . Нижче ми доведемо, що загальне число збільшень потоку, що виконується даним алгоритмом, становить . Таким чином, складність алгоритму Едмондса — Карпа дорівнює .

Доведення ред.

Назвемо відстанню від вершини до вершини довжину найкоротшого шляху від до в залишковій мережі. Якщо такого шляху немає, будемо вважати відстань нескінченною. Будемо говорити, що наблизився до (віддалився від ), якщо відстань від до зменшилася (збільшилася). Будемо говорити, що ближче до (далі від ), ніж , якщо відстань від до менше (більше), ніж відстань від до .

Лема ред.

У ході роботи алгоритму жодна вершина ніколи не наближається до початку.

Доказ. Нехай це не так, тоді при деякому збільшенні потоку деякі вершини наблизилися до джерела. Назвемо їх неправильними. Виберемо ту з неправильних вершин, яка після збільшення потоку виявилася ближче всіх до джерела (якщо таких більше однієї, то будь-яку з них). Позначимо вибрану вершину через v. Розглянемо найкоротший шлях від s до v. Позначимо передостанню вершину на цьому шляху через u, таким чином, шлях має вигляд s -…- uv. Оскільки u ближче до s, ніж v, а v — найближча до s з неправильних вершин, u — вершина правильна. Позначивши відстані від s до u і v до і після збільшення потоку відповідно через , , , , маємо:

,звідки

Отже, до збільшення потоку ребро (u, v) було відсутнім в залишковій мережі. Щоб воно з'явилося, збільшуваний шлях повинен був містити ребро (v, u). Але в алгоритмі Едмондса — Карпа збільшуємий шлях завжди найкоротший, отже,

, що суперечить попередній нерівності. Значить, наше припущення було невірним. Лема доведена.

Назвемо критичним те з ребер збільшуючого шляху, у якого залишкова пропускна здатність мінімальна. Оцінимо, скільки разів якесь ребро (u, v) може стати критичним. Нехай це відбулося на ітерації , а в наступній раз на ітерації . Позначаючи через відстань від s до y на ітерації t, маємо:

Зауважимо, що на ітерації критичне ребро зникає із залишкової мережі. Щоб до моменту ітерації ребро (u, v) в ній знову з'явилося, необхідно, щоб на якійсь проміжній ітерації був обраний збільшуючий шлях, що містить ребро (v, u).

Отже,

Використовуючи раніше доведену лемму, отримуємо:

Оскільки спочатку (інакше v = s, але ребро, провідне в s, не може з'явитися на найкоротшому шляху з s в t), і завжди, коли звичайно, воно менше V (найкоротший шлях не містить циклів, і, отже, містить менше V ребер), ребро може виявитися критичним не більше раз. Оскільки кожен збільшуючий шлях містить хоча б одне критичне ребро, а всього ребер, які можуть колись стати критичними, (всі ребра вихідної мережі і їм протилежні), то ми можемо збільшити шлях не більше EV раз. Отже, кількість ітерацій не перевищує O (EV), що потрібно було довести.

Приклад ред.

Нехай задана мережа з витоком у вершині і стоком в вершині . На малюнку парою позначений потік по цьому ребру і його пропускна спроможність.

Пошук в ширину ред.

Опишемо пошук в ширину на першому кроці.

  1. Черга складається з єдиної вершини A. Пройдена вершина A. Предків немає.
  2. Черга полягає (від початку до кінця) з вершин B і D. Пройдені вершини A, B, D. Вершини B D мають предка А.
  3. Черга складається з вершин D і C. Пройдені A, B, C, D. Вершини B, D мають предка А, вершина C — предка B.
  4. Черга складається з вершин C, E, F. Пройдені A, B, C, D, E, F. Вершини B, D мають предка А, вершина C — предка B, вершини E, F — предка D.
  5. Вершина C видаляється з черги: ребра з неї ведуть тільки у вже пройдені вершини .
  6. Можна знайти ребро (E, G) і цикл зупиняється. У черзі вершини (F, G). Відвідані всі вершини . Вершини B, D мають предка А, вершина C — предка B, вершини E, F — предка D, вершина G — предка E.
  7. Йдемо по предкам: G->E->D->A. Повертаємо пройдений шлях у зворотному порядку: А->D->E->G.

Зауважимо, що в чергу послідовно додавали вершини, досяжні з A рівно за 1 крок, рівно за 2 кроки, рівно за 3 кроки. Крім того, предком кожної вершини є вершина, досяжна з A рівно на 1 крок швидше.

Основний алгоритм ред.

Пропускна здатність шляху шлях












Відзначимо, що в процесі виконання алгоритму довжини доповнюючих шляхів (на малюнках позначені червоним) не зменшуються. Це властивість виконується завдяки тому, що ми шукаємо найкоротший доповнюючий шлях.

Алгоритм Дініца ред.

Покращеною версією алгоритму Едмондса-Карпа є алгоритм Дініца, що вимагає операцій.

Назвемо допоміжною безконтурною мережею графу G з джерелом s його підграф, що містить тільки такі ребра (u, v), для яких мінімальна відстань від s до v на одиницю більше мінімальної відстані від s до u.

Алгоритм Дініца:

  • Будуємо мінімальну безконтурну мережу остаточного графу.
  • Поки в мережі є шлях із s в t, виконати наступні кроки:
    • Знаходимо найкоротший шлях з s в t. Якщо його немає, вийти з циклу.
    • На знайденому шляху в остаточній мережі шукаємо ребро з мінімальною пропускною здатністю .
    • Для кожного ребра на знайденому шляху збільшуємо потік на , а в протилежному йому — зменшуємо на .
    • Видаляємо всі ребра, які досягли насичення.
    • Видаляємо всі глухі кути (тобто вершини, крім стоку, звідки не виходить ребер, і вершини, крім джерела, куди ребер не входить) разом з усіма інцидентними їм ребрами.
    • Повторюємо попередній крок, поки є що видаляти.
  • Якщо знайдений потік ненульовий, додаємо його до загального потоку і повертаємося на крок 1.

Посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Algoritm Edmondsa Karpa rozv yazuye zadachu znahodzhennya maksimalnogo potoku v transportnij merezhi Algoritm yavlyaye soboyu okremij vipadok metodu Forda Falkersona i pracyuye za chas O V E 2 displaystyle O V E 2 Vpershe buv opublikovanij v 1970 roci radyanskim vchenim Yu A Denicom Piznishe v 1972 roci buv nezalezhno vidkritij Edmondsom i Karpom Algoritm Dinica podaye dodatkovi pidhodi dlya zmenshennya chasu do O V 2 E displaystyle O V 2 E Zmist 1 Algoritm 1 1 Opis 2 Psevdokod 3 Skladnist 3 1 Dovedennya 3 2 Lema 4 Priklad 4 1 Poshuk v shirinu 4 2 Osnovnij algoritm 5 Algoritm Dinica 6 PosilannyaAlgoritm red Algoritm Edmondsa Karpa ce variant algoritmu Forda Falkersona pri yakomu na kozhnomu kroci vibirayut najkorotshij dopovnyuvalnij shlyah z s displaystyle s nbsp v t displaystyle t nbsp zalishkovoyi merezhi vvazhayuchi sho kozhne rebro maye odinichnu dovzhinu Najkorotshij shlyah znahodimo poshukom v shirinu Opis red Obnulyayemo vsi potoki Zalishkova merezha spochatku zbigayetsya z pochatkovoyu merezheyu U zalishkovij merezhi znahodimo najkorotshij shlyah z dzherela v stik Yaksho takogo shlyahu nemaye zupinyayemosya Puskayemo cherez znajdenij shlyah vin nazivayetsya zbilshuvalnim shlyahom abo zbilshuvalnim lancyugom maksimalno mozhlivij potik Na znajdenomu shlyahu v zalishkovij merezhi shukayemo rebro z minimalnoyu propusknoyu zdatnistyu c min displaystyle c min nbsp Dlya kozhnogo rebra na znajdenomu shlyahu zbilshuyemo potik na c min displaystyle c min nbsp a v protilezhnomu jomu zmenshuyemo na c min displaystyle c min nbsp Modifikuyemo zalishkovu merezhu Dlya vsih reber na znajdenomu shlyahu a takozh dlya protilezhnih yim reber obchislyuyemo novu propusknu zdatnist Yaksho vona stala nenulovoyu dodayemo rebro do zalishkovoyi merezhi a yaksho obnulilas stirayemo jogo Povertayemosya na krok 2 Shob znajti najkorotshij shlyah v grafi vikoristovuyemo poshuk v shirinu Stvoryuyemo chergu vershin O Spochatku O skladayetsya z yedinoyi vershini s Vidmichayemo vershinu s yak vidvidanu bez predka a vsi inshi yak nevidvidani Poki cherga neporozhnya vikonuyemo nastupni kroki Vidalyayemo pershu v cherzi vershinu u Dlya vsih reber u v sho vihodyat z vershini u takih sho vershina v she ne vidvidana vikonuyemo nastupni kroki Vidznachayemo vershinu v yak vidvidanu z predkom u Dodayemo vershinu v v kinec chergi Yaksho v t vihodimo z oboh cikliv mi znajshli najkorotshij shlyah Yaksho chergu porozhnya povertayemo vidpovid sho shlyahu nemaye vzagali i zupinyayemosya Yaksho ni jdemo vid t do s shorazu perehodyachi do predka Povertayemo shlyah u zvorotnomu poryadku Psevdokod red algorithm EdmondsKarp input C 1 n 1 n Yemnist matrici E 1 n 1 Susidni listi s Dzherelo t Stik output f Znachennya maksimalnoyi vitrati F Matricya daye pravovoyi potik z maksimalnim znachennyam f 0 Pochatkovij potik dorivnyuye nulyu F array 1 n 1 n Zalishkova yemnist vid u do v ce C u v F u v forever m P BreadthFirstSearch C E s t F if m 0 break f f m Povernitsya do poshuku i zapisati potik v t while v s u P v F u v F u v m F v u F v u m v u return f F algorithm BreadthFirstSearch input C E s t F output M t Znajshli yemnist shlyahu P Batkivska tablicya P array 1 n for u in 1 n P u 1 P s 2 Perekonajtesya sho dzherelo ne viyavleno M array 1 n Potuzhnist znajdenogo shlyahu do vuzla M s Q queue Q offer s while Q size gt 0 u Q poll for v in E u Yaksho ye vilna yemnist ta v ne zustrichavsya u poshuku if C u v F u v gt 0 and P v 1 P v u M v min M u C u v F u v if v t Q offer v else return M t P return 0 P psevdo kod Edmondsa Karpa z vikoristannyam sumizhnih vuzliv algorithm EdmondsKarp input graph Grafik spisku sumizhnosti vuzliv z produktivnistyu potik zvorotnij i napryamlenij s Dzherelo t Stik output flow Maksimalne znachennya potoku flow 0 Pochatkovij potik dorivnyuye nulyu q array 1 n Inicializaciya q yak grafu dovzhinu while true qt 0 Zminna dlya prohodu po vsih vidpovidnim rebram q qt s Inicializaciya pochatkovogo masivu pred array q length Inicializaciya poperednogo spisku z grafom dovzhini for qh 0 qh lt qt amp amp pred t null cur q qh for graph cur Prohid po vsim rebram Edge e graph cur Kozhne rebro maye buti pov yazane z yemnistyu if pred e t null amp amp e cap gt e f pred e t e q qt e t if pred t null break int df MAX VALUE Inicializaciya do maksimalnogo znachennya for u t u s u pred u s df min df pred u cap pred u f for u t u s u pred u s pred u f pred u f df pEdge array PredEdge pEdge graph pred u t pEdge pred u rev f pEdge pred u rev f df flow flow df return flowSkladnist red U procesi roboti algoritm Edmondsa Karpa bude znahoditi kozhen dopovnyuyuchij shlyah za chas O E displaystyle O E nbsp Nizhche mi dovedemo sho zagalne chislo zbilshen potoku sho vikonuyetsya danim algoritmom stanovit O V E displaystyle O VE nbsp Takim chinom skladnist algoritmu Edmondsa Karpa dorivnyuye O V E 2 displaystyle O VE 2 nbsp Dovedennya red Nazvemovidstannyu vid vershini x displaystyle x nbsp do vershini y displaystyle y nbsp dovzhinu najkorotshogo shlyahu vid x displaystyle x nbsp do y displaystyle y nbsp v zalishkovij merezhi Yaksho takogo shlyahu nemaye budemo vvazhati vidstan neskinchennoyu Budemo govoriti sho y displaystyle y nbsp nablizivsya do x displaystyle x nbsp viddalivsya vid x displaystyle x nbsp yaksho vidstan vid x displaystyle x nbsp do y displaystyle y nbsp zmenshilasya zbilshilasya Budemo govoriti sho y displaystyle y nbsp blizhche do x displaystyle x nbsp dali vid x displaystyle x nbsp nizh z displaystyle z nbsp yaksho vidstan vid x displaystyle x nbsp do y displaystyle y nbsp menshe bilshe nizh vidstan vid x displaystyle x nbsp do z displaystyle z nbsp Lema red U hodi roboti algoritmu zhodna vershina nikoli ne nablizhayetsya do pochatku Dokaz Nehaj ce ne tak todi pri deyakomu zbilshenni potoku deyaki vershini nablizilisya do dzherela Nazvemo yih nepravilnimi Viberemo tu z nepravilnih vershin yaka pislya zbilshennya potoku viyavilasya blizhche vsih do dzherela yaksho takih bilshe odniyeyi to bud yaku z nih Poznachimo vibranu vershinu cherez v Rozglyanemo najkorotshij shlyah vid s do v Poznachimo peredostannyu vershinu na comu shlyahu cherez u takim chinom shlyah maye viglyad s uv Oskilki u blizhche do s nizh v a v najblizhcha do s z nepravilnih vershin u vershina pravilna Poznachivshi vidstani vid s do u i v do i pislya zbilshennya potoku vidpovidno cherez d u displaystyle d u nbsp d u displaystyle d u nbsp d v displaystyle d v nbsp d v displaystyle d v nbsp mayemo d v lt d v displaystyle d v lt d v nbsp d u d u displaystyle d u geq d u nbsp d v d u 1 displaystyle d v d u 1 nbsp zvidki d v d u 2 displaystyle d v geq d u 2 nbsp Otzhe do zbilshennya potoku rebro u v bulo vidsutnim v zalishkovij merezhi Shob vono z yavilosya zbilshuvanij shlyah povinen buv mistiti rebro v u Ale v algoritmi Edmondsa Karpa zbilshuyemij shlyah zavzhdi najkorotshij otzhe d v d u 1 displaystyle d v d u 1 nbsp sho superechit poperednij nerivnosti Znachit nashe pripushennya bulo nevirnim Lema dovedena Nazvemo kritichnim te z reber zbilshuyuchogo shlyahu u yakogo zalishkova propuskna zdatnist minimalna Ocinimo skilki raziv yakes rebro u v mozhe stati kritichnim Nehaj ce vidbulosya na iteraciyi t 1 displaystyle t 1 nbsp a v nastupnij raz na iteraciyi t 2 displaystyle t 2 nbsp Poznachayuchi cherez D y t displaystyle D y t nbsp vidstan vid s do y na iteraciyi t mayemo D v t 1 D u t 1 1 displaystyle D v t 1 D u t 1 1 nbsp D v t 2 D u t 2 1 displaystyle D v t 2 D u t 2 1 nbsp Zauvazhimo sho na iteraciyi t 1 displaystyle t 1 nbsp kritichne rebro znikaye iz zalishkovoyi merezhi Shob do momentu iteraciyi t 2 displaystyle t 2 nbsp rebro u v v nij znovu z yavilosya neobhidno shob na yakijs promizhnij iteraciyi t 3 displaystyle t 3 nbsp buv obranij zbilshuyuchij shlyah sho mistit rebro v u Otzhe D u t 3 D v t 3 1 displaystyle D u t 3 D v t 3 1 nbsp Vikoristovuyuchi ranishe dovedenu lemmu otrimuyemo D v t 2 D u t 2 1 D u t 3 1 D v t 3 2 D v t 1 2 displaystyle D v t 2 D u t 2 1 geq D u t 3 1 D v t 3 2 geq D v t 1 2 nbsp Oskilki spochatku D v gt 0 displaystyle D v gt 0 nbsp inakshe v s ale rebro providne v s ne mozhe z yavitisya na najkorotshomu shlyahu z s v t i zavzhdi koli D v displaystyle D v nbsp zvichajno vono menshe V najkorotshij shlyah ne mistit cikliv i otzhe mistit menshe V reber rebro mozhe viyavitisya kritichnim ne bilshe V 1 1 2 1 V 2 displaystyle frac V 1 1 2 1 V 2 nbsp raz Oskilki kozhen zbilshuyuchij shlyah mistit hocha b odne kritichne rebro a vsogo reber yaki mozhut kolis stati kritichnimi 2 E displaystyle 2E nbsp vsi rebra vihidnoyi merezhi i yim protilezhni to mi mozhemo zbilshiti shlyah ne bilshe EV raz Otzhe kilkist iteracij ne perevishuye O EV sho potribno bulo dovesti Priklad red Nehaj zadana merezha z vitokom u vershini A displaystyle A nbsp i stokom v vershini G displaystyle G nbsp Na malyunku paroyu f c displaystyle f c nbsp poznachenij potik po comu rebru i jogo propuskna spromozhnist nbsp Poshuk v shirinu red Opishemo poshuk v shirinu na pershomu kroci Cherga skladayetsya z yedinoyi vershini A Projdena vershina A Predkiv nemaye Cherga polyagaye vid pochatku do kincya z vershin B i D Projdeni vershini A B D Vershini B D mayut predka A Cherga skladayetsya z vershin D i C Projdeni A B C D Vershini B D mayut predka A vershina C predka B Cherga skladayetsya z vershin C E F Projdeni A B C D E F Vershini B D mayut predka A vershina C predka B vershini E F predka D Vershina C vidalyayetsya z chergi rebra z neyi vedut tilki u vzhe projdeni vershini Mozhna znajti rebro E G i cikl zupinyayetsya U cherzi vershini F G Vidvidani vsi vershini Vershini B D mayut predka A vershina C predka B vershini E F predka D vershina G predka E Jdemo po predkam G gt E gt D gt A Povertayemo projdenij shlyah u zvorotnomu poryadku A gt D gt E gt G Zauvazhimo sho v chergu poslidovno dodavali vershini dosyazhni z A rivno za 1 krok rivno za 2 kroki rivno za 3 kroki Krim togo predkom kozhnoyi vershini ye vershina dosyazhna z A rivno na 1 krok shvidshe Osnovnij algoritm red Propuskna zdatnist shlyahu shlyahmin c f A D c f D E c f E G displaystyle min c f A D c f D E c f E G nbsp min 3 0 2 0 1 0 displaystyle min 3 0 2 0 1 0 nbsp min 3 2 1 1 displaystyle min 3 2 1 1 nbsp A D E G displaystyle A D E G nbsp nbsp min c f A D c f D F c f F G displaystyle min c f A D c f D F c f F G nbsp min 3 1 6 0 9 0 displaystyle min 3 1 6 0 9 0 nbsp min 2 6 9 2 displaystyle min 2 6 9 2 nbsp A D F G displaystyle A D F G nbsp nbsp min c f A B c f B C c f C D c f D F c f F G displaystyle min c f A B c f B C c f C D c f D F c f F G nbsp min 3 0 4 0 1 0 6 2 9 2 displaystyle min 3 0 4 0 1 0 6 2 9 2 nbsp min 3 4 1 4 7 1 displaystyle min 3 4 1 4 7 1 nbsp A B C D F G displaystyle A B C D F G nbsp nbsp min c f A B c f B C c f C E c f E D c f D F c f F G displaystyle min c f A B c f B C c f C E c f E D c f D F c f F G nbsp min 3 1 4 1 2 0 0 1 6 3 9 3 displaystyle min 3 1 4 1 2 0 0 1 6 3 9 3 nbsp min 2 3 2 1 3 6 1 displaystyle min 2 3 2 1 3 6 1 nbsp A B C E D F G displaystyle A B C E D F G nbsp nbsp Vidznachimo sho v procesi vikonannya algoritmu dovzhini dopovnyuyuchih shlyahiv na malyunkah poznacheni chervonim ne zmenshuyutsya Ce vlastivist vikonuyetsya zavdyaki tomu sho mi shukayemo najkorotshij dopovnyuyuchij shlyah Algoritm Dinica red Pokrashenoyu versiyeyu algoritmu Edmondsa Karpa ye algoritm Dinica sho vimagaye O V 2 E displaystyle O V 2 E nbsp operacij Nazvemo dopomizhnoyu bezkonturnoyu merezheyu grafu G z dzherelom s jogo pidgraf sho mistit tilki taki rebra u v dlya yakih minimalna vidstan vid s do v na odinicyu bilshe minimalnoyi vidstani vid s do u Algoritm Dinica Buduyemo minimalnu bezkonturnu merezhu ostatochnogo grafu Poki v merezhi ye shlyah iz s v t vikonati nastupni kroki Znahodimo najkorotshij shlyah z s v t Yaksho jogo nemaye vijti z ciklu Na znajdenomu shlyahu v ostatochnij merezhi shukayemo rebro z minimalnoyu propusknoyu zdatnistyu c min displaystyle c min nbsp Dlya kozhnogo rebra na znajdenomu shlyahu zbilshuyemo potik na c min displaystyle c min nbsp a v protilezhnomu jomu zmenshuyemo na c min displaystyle c min nbsp Vidalyayemo vsi rebra yaki dosyagli nasichennya Vidalyayemo vsi gluhi kuti tobto vershini krim stoku zvidki ne vihodit reber i vershini krim dzherela kudi reber ne vhodit razom z usima incidentnimi yim rebrami Povtoryuyemo poperednij krok poki ye sho vidalyati Yaksho znajdenij potik nenulovij dodayemo jogo do zagalnogo potoku i povertayemosya na krok 1 Posilannya red Realizaciya algoritmu Edmondsa Karpa na C na sajti e maxx ru Arhivovano 28 kvitnya 2015 u Wayback Machine Vizualizaciya algoritmu Realizaciya poshuku maksimalnogo potoku metodom Edmondsa Karpa na Java Arhivovano 18 kvitnya 2015 u Wayback Machine Otrimano z https uk wikipedia org w index php title Algoritm Edmondsa Karpa amp oldid 38153429