Page 88 - 2589

1) Кожна вершина x позначається індексом  . Спочатку
i i
кінцевій вершині  приписується індекс   0. Для інших
0 0
вершин заздалегідь вважаємо    ( i 0 ).
i
2) Шукаємо таку дугу (x , x ), для якої     l (x , x ) і
i j j i i j
'
замінюваний індекс  індексом  j   i  l( x , x )  .
j
j
i
j
Продовжуємо цей процес заміни індексів до тих пір, поки
залишається хоч би одна дуга, для якої можна зменшити  .
j
Відмітимо одно важливу властивість, якою будуть володіти

приписані вершинам індекси. Нехай x - довільна вершина. При
p
розглянутому процесі приписування індексів індекс 
p
монотонно зменшується. Нехай x - остання вершина, що
p
послужила для його зменшення. Тоді  p   q  l (x q , x p ). Отже,

для довільної вершини x з індексом  знайдеться вершина x ,
p p q
сполучена ребром з x , така, що  p   q  l (x q , x p ).
p
Ця властивість дозволяє сформулювати наступне правило для
знаходження найкоротшого шляху.
Ця властивість дозволяє сформулювати наступне правило для
знаходження найкоротшого шляху.

Нехай x  a  початкова вершина з індексом . Шукаємо
n n
вершину x , таку що     l (x , x ). Далі шукаємо
p 1 n p 1 p 1 n
вершину x , таку що    l (x , x ) і так далі, доки не
p
2 p 1 p 2 p 2 p 1
дійдемо до кінцевої вершини x  x  . b Шлях
p
k 1 0
  (x , x ,..., x , x ), довжина якого рівна  є найкоротшим.
0 n p p 0 n
1 k
Для підтвердження розглянемо довільний шлях із a в b:

  (x , x ,..., x , x ). Його довжина буде (l ). Відповідно правилу
n k 1 k s 0
розстановки індексів будуть виконуватися наступні нерівності:
    (xl , x ); 
n k 1 n 1 k 1
    (xl , x ); 
k 1 k 2 k 1 k 2 

.......... .......... .......... .....

  0  (xl , x ); 
k s k s 0 
Складаючи почленно ці нерівності, знаходимо, що для будь-
якого шляху µ має місце

  0  l ( )
n
88