Материал: 62_201

Отже, вихід знайдено і процес пошуку доповнюючого шляху з витоку до стоку, що можливо збільшить шуканий потік, роз­ блоковано. Дивимося з вершини 2 і бачимо нову вершину 5. У неї можна передати ще 5 одиниць води, які віртуально надійшли з вершини 4, а реально зекономлені у вершині 2. Зауважимо, що резерв ребра (2,5) становить на даний момент 10 одиниць води, однак у вершину 5 може прийти лише 5 оди­ ниць, які додатково подаються з вершини 2. Ставимо мітку [2,5] біля вершини 5 і дописуємо цю вершину у послідовність (мал. 92, а).

Тепер уже з вершини 5 видно стокову вершину 6. Вона буде позначена міткою [5,2], оскільки резерв ребра (5,6) обмежений величиною потоку 2. Таким чином, у вершину 6 надійшло ще 2 одиниці води (мал. 92, б).

Сумарна кількість води, яку нам вдалося пропустити мере­ жею, виконавши чотири ітерації, становить 22. На малюнку 93, а виділеними ребрами зображено отриманий доповнюючий пілях від витоку до стоку, що дає змогу проштовхнути мере­ жею ще 2 одиниці води.

Логічно було б прибрати уявне ребро (4,2) з мережі, оскіль­ ки воно вже виконало свою функцію. Для цього досить просумувати значення потоків, що рухаються прямим ребром (2,4)

145

Мал. 93

та зворотним (4,2), і отримати такий результат: ребро (2,4) у мережі насичене на 8 одиниць води з 10 можливих (мал. 93, б).

П'ята ітерація

У стоковій вершині 6 отримано очікувані 22 одиниці води. Однак необхідно виконати ще одну ітерацію для того, щоб пе­ реконатися, що немає більше доповнюючого шляху від вито­ ку 1 до стоку 6, який би збільшив потік у мережі і зміг би про­ штовхнути ще одну порцію води.

Почнемо рух з вершини 1. З неї можна пройти лише до вер­ шини 3, оскільки резерв ребра (1,3) становить 23 одиниці. З вершини 3 можна рухатися лише у напрямі вершини 4 (ре­ зерв ребра (3,4) - 3 одиниці). З вершини 4 можна перейти до вершини 2 зворотним ребром (4,2), насиченість якого дорівнює від'ємному значенню насиченості прямого ребра (2,4), тобто - 8, і пропустити ті самі 3 одиниці води, що надійшли у вершину 4. Перейшовши у вершину 2, рухаємося далі у вершину 5: резерв ребра (2,5) дає змогу це зробити. І на цьому наш рух припи­ няється, оскільки з вершини 5 можна перейти лише у верши­ ну 6, однак ребро (5,6) вже максимально насичене (мал. 94, а).

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

146

води. Це означає, що значення максимального потоку 22 отри­ мано і визначені насиченості кожного ребра мережі (мал. 94, б).

Аналізуючи отриманий результат, слід відзначити, що у ме­ режі залишилося тільки одне незадіяне порожнє ребро (5,4). Слушним є запитання: а чому під час виконання п'ятої ітерації не була здійснена спроба по ньому пустити воду в зворотному напрямі? Відповідь буде такою: потік можна пускати у зворот­ ному напрямі тільки тоді, коли вже існує потік цим ребром у прямому напрямі. Така відповідь пояснюється тим, що наяв­ ність зворотного напряму потоку відповідає зменшенню потоку в прямому напрямі, а що ж можна зменшити, якщо потоку зовсім немає.

Сформулюємо алгоритм метода Форда-Фалкерсона.

1.Почати перегляд вершин мережі з вершини-витоку s і визначити її як поточну відвідану.

2.Визначити вершини мережі, які можна побачити з поточ­ ної відвіданої вершини.

3.Якщо такі вершини є і серед них відсутня верпіина-стік t, то надати їм статус «побачених» і позначити відповідними міт­ ками. У протилежному разі перейти до п. 6.

4.Перейти до першої з послідовності «побачених» вершин і визначити її статус як відвіданої.

5.Перейти до п. 2.

6.Якщо статус «побаченої» вершини отримала вершинастік, то збільшити потік у мережі на значення потоку, що наді­ йшов до вершини t, і додати це значення до значень поточної насиченості всіх ребер, з яких складається визначений допов­ нюючий шлях від вершини-витоку s до вершини-стоку t. Пе­ рейти до п. 1.

7.Якщо у послідовності «побачених» вершин відсутня вер- шина-стік t і до послідовності «побачених» вершин немає мож­ ливості приписати жодної нової вершини, то значення макси­ мального потоку в мережі визначається значенням потоку, що отриманий у вершині-стоку t.

8.Завершити алгоритм.

Перейдемо безпосередньо до реалізації описаного алгорит­ му мовою програмування. Відмінність програми від алгоритму подекуди буває досить значною. Метод, який лежить в основі й алгоритму, і програми, один і той самий, а от для безпосе­ редньої реалізації алгоритму у вигляді програми необхідно ввести додаткові змінні, умови аналізу тих чи інших поточних ситуацій.

Вхідна інформація про задану мережу міститиметься у дво­ вимірному масиві С[і, j], а інформація про поточний стан наси­ ченості ребер - у двовимірному масиві F[i, j]. Різниця між від-

147

повідними елементами цих масивів свідчитиме про резерв на­ сиченості кожного ребра.

Послідовність відвіданих та «побачених» вершин являє собою структуру даних «черга», і для її організації виділяється одновимірний масив q. Оскільки кожна «побачена» вершина мережі отримує мітку у вигляді номера вершини, з якої її було побаче­ но, і величини потоку, який може у неї прийти, то для збере­ ження цієї інформації організовано масив Ibl типу record, перше поле якого містить номер вершини-предкаргеи, а друге - зна­ чення потоку flow. Як ми бачили у раніше розглянутому прикла­ ді (можна звернути увагу на два останні кроки п'ятої ітерації), значення змінної flow обирається як мінімальне між тим пото­ ком, який ще можна пропустити ребром (u,u) (C[u,u] - F[u,v]), і тим, що прийшов у вершину и.

Сенс усіх досі визначених змінних повністю відповідає опи­ саному вище алгоритму. Тепер розглянемо питання фіксації зворотних, тобто віртуальних, ребер. У прикладі зворотне ребро

148

введено у той момент, коли виникла безвихідна ситуація: виявилася недосяжною вершина-стік. Пошук вершини на де­ якому етапі виконання програми, в якій можна було б перероз­ поділити потік, - зайва трата часу. Тому, оскільки наперед невідомо, для якого прямого ребра з'явиться потреба у вико­ ристанні його зворотного близнюка, будемо про всяк випадок зберігати зворотне значення для кожного ребра, для якого об­ числюється значення потоку. Тобто для прямого ребра (и, v) зберігатимемо інформацію F[u, v], а для відповідного йому зво­ ротного ребра (и, и) - від'ємне значення -F[u, v]. На малюн­ ку 95 зображено стани масиву F після виконання кожної з чо­ тирьох результативних ітерацій.

Таким чином, шукаючи з поточної відвіданої вершини і наступну видиму вершину ;', розглядатимемо як прямі ребра, для яких насиченість ще не перевищила пропускної спромож­ ності С[і, j] - F[i, j] > 0, так і зворотні з ненульовими значення­ ми, що свідчитиме про існування відповідного прямого ребра. Оскільки зворотні ребра у масиві С не визначені, тобто С[і, j] = 0 (їх у мережі немає), а у масиві F вони визначені від'ємними числами F[i,j] < 0, то вираз С[і, j] - F[i, j] так само буде додат­ ним: С[і, j] - F[i, j] > 0. Отже, умова існування потоку ребром (і, j) однакова як для прямих, так і для зворотних ребер.

Підбиваючи підсумок усього вищесказаного, можна запро­ понувати такий компактний і зрозумілий запис алгоритму Форда-Фалкерсона:

Поки існує доповнюючий шлях з вершини-витоку до вершини-стоку, виконати:

визначити значення потоку у вершині-стоку flowt;

для кожного ребра (u,v) знайденого доповнюючого шляху виконати:

F[u,v] := F[u,v] + flowt; F[v,u] := -F[u,v] + flowt;

Удосконаленням методу Форда-Фалкерсона вважається використання алгоритму пошуку в ширину для визначення найкоротшого шляху від вершини-витоку до вершини-стоку, запропонований Едмондеоном і Карпом.

Пропонується такий можливий варіант реалізації процедури проходження мережею від витоку s до стоку t для пошуку до­ повнюючого шляху, який дасть можливість збільшити потік:

procedure marking(var new_flow: integer); begin

while (head < tail) and not flag do {Поки «голова» черги менша від «хвоста»}

149