Page 76 - 4336

0
d 1 1 , 1  ((d 1 1 , 1  V )  (d 1 2 , 1  d 0 1 , 2 )  (d 1 3 , 1  d 0 1 , 3 ))  d ,
1 , 1

d 1 2 , 1  ((d 1 1 , 1  V )  (d 1 2 , 1  V )  (d 1 3 , 1  d 0 2 , 3 ))  d 0 2 , 1 ,

d 1  ((d 1  V )  (d 1  V )  (d 1  V ))  d 0 .
3 , 1 1 , 1 2 , 1 3 , 1 3 , 1

Враховуючи співвідношення (4.11) та (4.12):

d 1 1 , 1  (V  (d 1 2 , 1  d 0 1 , 2 )  (d 1 3 , 1  d 0 1 , 3 ))  d 0 1 , 1  ((d 1 2 , 1  d 0 1 , 2 ) 

0
 (d 1 3 , 1  d 0 1 , 3 ))  d ,
1 , 1

d 1 2 , 1  (V  V  (d 1 3 , 1  d 0 2 , 3 ))  d 0 2 , 1  (d 1 3 , 1  d 0 2 , 3 )  d 0 2 , 1 ,

d 1  (V  V  V )  d 0  V  d 0  d 0 .
3 , 1 2 , 1 2 , 1 3 , 1

Таким чином, для знаходження усіх векторів оцінюючого

рядка , необхідно починати пошук з останнього елемента

вектора – .
,
Після того як будуть знайдені довжини шляхів, виконується

процедура трасування, що дозволяє визначити відповідні шляхи.

Суть її полягає в наступному. Припустимо, що потрібно знайти

m-й найкоротший шлях із початкової вершини в вершину i.

Нехай , – довжина цього шляху і нехай вершина j з'єднана

дугою з вершиною i. Тоді

d m ,i  d t , j  d ( ) ,i j (4.16)

де – довжина дуги (j, i), – довжина t-гo найкоротшого
,
,
шляху з початкової вершини у вершину j (t≤m). Для кожної

вершини i процедура трасування полягає в пошуку вершини j,

для якої виконується співвідношення (4.16). Як тільки вузол j

буде знайдений, необхідно знову повернутись до даної процедури

і виконувати її доти, поки не буде досягнуто початкової вершини.

76