Алгоритм Форда-Фалкерсона
Алгоритм Форда-Фалкерсона також складається з двох кроків: завдання початкових умов і розрахунок найкоротших відстаней. Формування маршрутів, порівняно з алгоритмом Дейкстри, здійснюється у зворотному порядку — від вузла одержувача до всіх інших вузлів. Алгоритм закінчує свою роботу, коли для всіх вузлів фіксується відстань до вузла одержувача і на найкоротшому шляху в напрямку одержувача позначаються наступні вузли. Внаслідок цього для кожного i‑го вузла обчислюється значення (k,Dj,i), де k — номер наступного вузла від поточної (i‑ї) вершини у напрямку кінцевого вузла (Aj). На початковому (першому) етапі вибирається вузол призначення Aj, для якого встановлюється значення Dі,j = 0 і позначаються ( - , - ) всі інші вузли. На другому і наступних етапах, відповідно до умови Dj,i=(min[Dj,i, Dj,k+Lk,i]), обчислюються та коригуються маршрути для кожної i‑ої вершини. Вибір мінімального шляху здійснюється в усіх напрямках (ребрах), що ведуть з вершини, для якої на даний момент розраховується маршрут.
Розглянемо роботу алгоритму на прикладі мережі, зображеної на рис. 8.4. Вузлом призначення вибираємо перший вузол, D1,1 = 0, всі інші вузли одержують позначки ( . , - ). Одержані значення вносяться у таблицю маршрутів (табл. 8.2).
Таблиця 8.2. Таблиця маршрутів алгоритму Форда-Фалкерсона
| Крок ітерації | Мітки вузлів | ||||
| (- , -) | (- , -) | (- , -) | (. , -) | (. , -) | |
| (1,2) | (1,1) | (- , -) | (1,4) | (- , -) | |
| (1,2) | (1,1) | (2,3) | (3,3) | (5,5) |
На другому кроці обчислюються значення для другого (1,2), третього (1,1) та п’ятого (1,4) вузлів. На наступному етапі для четвертого вузла можуть бути визначені два шляхи з трьох можливих: через другий і третій вузли. Довжина шляху через другий вузол (D1,2+L2,4) = (2+1) дорівнює трьом, а через третій (D1,3+L3,4) — чотирьом, отже, для аналізованого вузла формується шлях через другий вузол, що визначається позначкою (2,3). Для п’ятого вузла з двох доступних шляхів вибирається шлях через третю вершину і формується позначка (3,3). Відповідно, для шостої вершини з двох шляхів вибирається мінімальний шлях через п'яту вершину — формується мітка (5,5). На третьому кроці прораховуються інші шляхи, що стали доступними, проте у нашому прикладі вони не призводять до змін у таблиці маршрутів.
Алгоритми Дейкстри і Форда-Фалкерсона стали вихідною точкою для створення численних сучасних алгоритмів маршрутизації.
Дата добавления: 2015-08-11; просмотров: 751;