Page 34 - 2577

або
N N T N N * T
  kl   kl . (2.21)
f
k  1 l 1 f kl k  1 l 1 f kl

Таким чином, для того, щоб в результаті ітерацій потік f наближався до
оптимального розв'язку необхідно, щоб Т  0 , а це означає, що нерівність (2.21)
перетворюється у рівність. Звідси висновок: для розв'язку задачі (2.11) необхідно
мінімізувати величину
N N T
T( )   ,
 kl f
k  l1 1 kl
де  - потік по найкоротшим маршрутом, який визначається у відповідності з вагами
kl
w . Із рівняння (2.11) випливає, що
kl
 T d
w   kl .
kl 2
f  kl d  f kl 
kl
Наведемо одну із версій алгоритму розв`язку задачі оптимальної маршрутизації, яка
запропонована В.М.Вишневським.

Алгоритм Вишневського

Для знаходження оптимального маршруту необхідно здійснити таку послідовність
кроків:
К1. Визначити ваги ліній зв'язку w та ініціалізувати потоки в лініях зв'язку
kl
  T 1
  , k ,l  , 1 N , d  0
kl
w   f  kl f kl 0 d kl
kl

  , k ,l  , 1 N d  0
kl
f  ; 0 k ,l  , 1 . N
kl
К1. Використовуючи ваги ліній зв'язку w , визначити найкоротші шляхи  між
kl ij
всіма парами вузлів „джерело - адресат”. Для знаходження найкоротших шляхів слід
скористатись ФУ – алгоритмом.
К2. Розподілити потоки за найкоротшими шляхами.
 i, j 1 , N :
 lk ,   - вибираємо ті шляхи із всіх можливих, які є найкоротшими і для них
ij
обчислюємо
 ij
f :  f  .
kl
kl

.
Значення f обчислюємо для шляхів 
kl ij
К3. Обчислюємо
1 N N f
T old  :  kl .
 d  f
k  l1 1 kl kl
К4. Покласти   1 : . 
К5. Покласти
   1 
 2
 : min  ,  , 
  max 

31