Page 51 - 4336

а а б в

г д

Рисунокк 4.7.

Крок 3. Оскілльки поззначені нне всі веершини,, то перееходимоо

до ккроку 2.

Крок 2. (y=b)). Розрааховуємоо величиину d(x)) для кожної зз

вершини (ккрім вершшини b) за форммулою (44.1):

0 3; 
d (a )  min{ ( d a );d (b )  ( c b ,a )}}  min{0  }  0 ;

)  min{d
d (c  (c);dc (b  , )} min{ 4 3;   }  4 ;
)  ( cbc
d (d )  min{ ( d(d );d (b )  c (b , ) d }  min{ ;  3 } 1  ;
4
d (e  (e);de (b  , )}  min{ 3;  } 1  4 .
)  min{d
)  ( ebc
Для рраніше позначеної веершини a значчення dd(a) нее

зміннилось, тому позначка з неї нне знімаається. ДДля всіхх іншихх
вершин c, dd та e знначення d(x) рівнні між собою, тоому познначаємоо

доввільну з дданих веершин, ннаприкллад вершшину c і ввідповіддну дугуу
(a, c). Приисвоюєммо у=c. Поточнее деревоо найкороротших шляхівв

склладайся зз дуг (a, b) і (a, cc) (рис. 44.7, б).
Крок 3. Оскілльки поззначені нне всі веершини,, то перееходимоо

до ккроку 2.
Крок 2. (y=c)). Розрааховуємоо величиину d(x)) для кожної зз

вершини (ккрім вершшини c) за форммулою (44.1):

51