З математичної точки зору задача про максимальний потік формулюється в такий спосіб: при заданій конфігурації мережі і відомої пропускної здатності знайти ненегативні значення , що задовольняють умовам і, що максимізують функцію , тобто
Алгоритм для знаходження максимального потоку був запропонований Фордом і Фалкерсоном і полягає в поступовому збільшенні потоку, що пропускається по мережі, доти, поки він не стане найбільшим. Алгоритм заснований на теоремі Форда-фалкерсона: у будь-якій транспортній мережі максимальний потік із джерела в стік , дорівнює мінімальній пропускній здатності розрізу, що відокремлює від .
Крок 0. Призначаємо вузлові 15 постійну мітку [0, -].
Крок 1. З вузла 15 можна досягти вузлів 21 2 12. Обчислюємо мітки для цих вузлів, у результаті одержуємо наступну таблицю міток:
Вузол
Мітка
Статус мітки
15
Постійна
21
[512,15]
Тимчасова
2
[237,15]
Серед вузлів 21, 2, 12, вузол 12 має найменше значення відстані (U12=172). Тому статус мітки цього вузла змінюється на «постійна».
Крок 2. З вузла 12 можна потрапити у вузли 2, 23, 22. Одержуємо наступний список вузлів.
Тимчасовий статус мітки [237,15] вузла 2 заміняється на постійний (U2=237).
Крок 3. З вузла 2 можна досягти вузлів 21, 22, 31. Після обчислення міток одержимо наступний їх список:
12
[172,15]
[370+512,2]=[882,2]
22
[1009,12]
[696+237,2]=[933,2]
23
[810,12]
31
[655+237,2]=[892,2]
Тимчасовий статус мітки [512,15] вузла 21 заміняється на постійний (U21=512).
Крок 4. З вузла 21 можна досягти вузлів 31. Після обчислення міток одержимо наступний їх список:
[933,2]
[892,2]
[512+289,21]= [801,21]
Тимчасовий статус мітки [801,21] вузла 31 заміняється на постійний (U31=801).
Крок 5. З вузла 31 можна досягти вузлів 22, 38. Після обчислення міток одержимо наступний їх список:
[801,21]
[801+237,31]= [1038,31]
38
[801+197,31]= [992,31]
Тимчасовий статус мітки [810,12] вузла 23 заміняється на постійний (U23=810).
Крок 6. З вузла 23 можна досягти вузла 22, 38, 3. Після обчислення міток одержимо наступний їх список:
[810+535,23]= [1345,23]
[992,31]
[810+929,23]= [1739,23]
3
[810+1045,23]= [1855,23]
Тимчасовий статус мітки [933,2] вузла 22 заміняється на постійний (U22=933).
Крок 7. З вузла 22 можна досягти вузлів 38, 3. Після обчислення міток одержимо наступний їх список:
[933+427,22]= [1360,22]
[1855,23]
[933+938,22]= [1871,22]
Страницы: 1, 2, 3, 4, 5
