Page 39 - 2577

 ,1 при l  i
N N 
j
x i, ( j)  x i, ( j)  , 0 при l  i, , (2.38)
 kl  lk 
k 1 k 1  , 1 при l  j

0  x kl , (i ) j  1; k ,, i l , j 1 , N , (2.39)
 N i, ( j)
x
 , 1 якщо  kl  0
( j)   i 1
v kl   N , (2.40)
 , 0 якщо x  ;0 j, k, l  N,1
  kl
  i 1
N
v ( j)  K, k, j  N,1 (2.41)
 kl
 l 1
Для розв’язку задачі (2.35) – (2.41) може бути запропонований алгоритм аналогічний
алгоритму дейтаграмної (багатошляхової) маршрутизації. Відмінність полягає в тому, що
відхилення потоку виконується не для всіх пар «джерело - адресат» одночасно, а для кожної
пари окремо.
Алгоритм К– шляхової маршрузації
К1. Визначити ваги ліній зв’язку
 T 1
  , k ,l  ,1 N : d  0
w kl  : f kl f kl 0 d kl kl ;
 , k ,l  ,1 N : d  0
 kl
та ініціалізувати потоки
f : ; 0 k, l 1 , N
kl
К1. Покласти:
 ij : 0 , де  - множина оптимальних маршрутів між парами вузлів i,j; ji,  , 1 N .
ij
V ( ) j : ; 0 j, k, l 1 , N .
kl
0
К2. Використовуючи ваги ліній зв’язку w kl визначити найкоротші маршрути  між
ij
всіма парами вузлів «джерело – адресат».
0
Включити  в множину  :
ij
ij
0
 ij   ij i, , j 1 , N .
К3. Розподілити потоки по найкоротших шляхах:
 i , j  , 1 N :  (k ,l )  ij 0 ;


1) f :  f  ij ;
kl
kl

2) якщо v ( kl ) j  0 , то v ( kl ) j  1
К4. Обчислити:
N
1 f
T  :  kl .
0 ld
 d  f
k,  l 1 kl kl
К5. Покласти:
 (i )  :  .
К7. Покласти:
  ) 1 ( 
 ) 2 ( :  min  ,  ,
  max 

36