Алгоритм Форда-Фалкерсона

Алгоритм Форда-Фалкерсона також складається з двох кроків: завдання початкових умов і розрахунок найкоротших відстаней. Формування маршрутів, порівняно з алгоритмом Дейкстри, здійснюється у зворотному порядку — від вузла одержувача до всіх інших вузлів. Алгоритм закінчує свою роботу, коли для всіх вузлів фіксується відстань до вузла одержувача і на найкоротшому шляху в напрямку одержувача позначаються наступні вузли. Внаслідок цього для кожного i‑го вузла обчислюється значення (k,D_j,i), де k — номер наступного вузла від поточної (i‑ї) вершини у напрямку кінцевого вузла (A_j). На початковому (першому) етапі вибирається вузол призначення A_j, для якого встановлюється значення D_і,j = 0 і позначаються ( - , - ) всі інші вузли. На другому і наступних етапах, відповідно до умови D_j,i=(min[D_j,i, D_j,k+L_k,i]), обчислюються та коригуються маршрути для кожної i‑ої вершини. Вибір мінімального шляху здійснюється в усіх напрямках (ребрах), що ведуть з вершини, для якої на даний момент розраховується маршрут.

Розглянемо роботу алгоритму на прикладі мережі, зображеної на рис. 8.4. Вузлом призначення вибираємо перший вузол, D_1,1 = 0, всі інші вузли одержують позначки ( . , - ). Одержані значення вносяться у таблицю маршрутів (табл. 8.2).

Таблиця 8.2. Таблиця маршрутів алгоритму Форда-Фалкерсона

На другому кроці обчислюються значення для другого (1,2), третього (1,1) та п’ятого (1,4) вузлів. На наступному етапі для четвертого вузла можуть бути визначені два шляхи з трьох можливих: через другий і третій вузли. Довжина шляху через другий вузол (D_1,2+L_2,4) = (2+1) дорівнює трьом, а через третій (D_1,3+L_3,4) — чотирьом, отже, для аналізованого вузла формується шлях через другий вузол, що визначається позначкою (2,3). Для п’ятого вузла з двох доступних шляхів вибирається шлях через третю вершину і формується позначка (3,3). Відповідно, для шостої вершини з двох шляхів вибирається мінімальний шлях через п'яту вершину — формується мітка (5,5). На третьому кроці прораховуються інші шляхи, що стали доступними, проте у нашому прикладі вони не призводять до змін у таблиці маршрутів.

Алгоритми Дейкстри і Форда-Фалкерсона стали вихідною точкою для створення численних сучасних алгоритмів маршрутизації.