Page 32 - 2577

Рис 2.7 – Передача повідомлень від вузлів 1, 2, ..., k до вузла–адресата j.

Алгоритм Флойда – Уоршела. Для
розв`язку основної задачі оптимальної
маршрутизації нам необхідно буде
розв`язати деяку проміжну задачу, в якій
потрібно знайти найкоротші шляхи для всіх
пар вузлів. Для розв'язку цієї задачі
використовується алгоритм Флойда –
Уоршела (ФУ-алгоритм). Змінними в ФУ-
алгоритмі є множина вузлів, які необхідно
мати як проміжні вузли на шляхах. Нехай
необхідно знайти найкоротший шлях між
двома вузлами. Позначимо їх через і та j
(рис. 2.8), де і- початок шляху, j - кінець.
Робота ФУ-алгоритму починається з
віддалей із однієї дуги (тобто без
Рисунок 2.8 – Мережа, в якій необхідно
проміжних вузлів)), які вибрані як вихідні
знайти найкоротші шляхи
оцінки для довжин найкоротших шляхів.

Потім знаходять найкоротші шляхи з тим
обмеженням, що проміжними є два, три і
т.д. вузли.
Для формалізованого опису задачі позначимо через  ij (n ) довжину найкоротшого

шляху від вузла і до вузла j за умови, що тільки п (п=1,2,...) вузлів можуть бути проміжними
на шляху. Тоді ФУ-алгоритм складається із таких кроків:

К1. Покласти  (n )  w  , i ; j i  , j де w - вага лінії зв`язку.
ij ij ij
К1. Для п= 0, 1, ..., N-1 обчислити
(n
 ij (n ) 1  min   ij (n ) , i (n ) 1  n ) , 1 j  ,  i  . j
,n
Так як кожний із N кроків проводиться для кожної пари вузлів, то об`єм обчислень
3
ФУ – алгоритму складає О( N ).

Алгоритм вибору оптимальних маршрутів у мережі
Альтернативна маршрутизація. Задача вибору оптимальних маршрутів у мережі
відноситься до класу багато продуктивних (багатовимірних) задач з випуклою цільовою
функцією і випуклою множиною обмежень. Це означає, що існує єдиний мінімум такої
задачі, який є глобальним. Алгоритми розв'язку задачі вибору оптимальних маршрутів
ґрунтуються на таких двох властивостях:
Властивість 1. Обмеження в задачі утворюють випуклу множину, крайніми точками
(рис. 2.7) якого є „екстремальні” потоки, які визначають відповідно до принципу найкращих
маршрутів. Суть цього принципу полягає в тому, що як оптимальні маршрути для кожної
пари „джерело (і) – адресат (j)” розглядаються найкоротші маршрути, які визначаються при

29