Page 46 - 4336

Рисуунок 4.3.

Роозв'язок.

Кррок 1. Поозначаєммо вершиину v. Вважаємоо, що d(vv)=0, d(xx)=∞
для всіхх вершинн х, які нне збігаюються з vv. Присвооюємо уу=v.

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

непознаачених ввершинии за форммулою (44.1):

( d(a )  minn{d (a );d )(v  c (v )},av  m min{ 0 ;  }4  4 ;

( d(b )  minn{d (b );d )(v  c (v )},b  miin{ 0 ;  }7  7;

( d(c )  minn{d (c );d )(v  c (v )},c  miin{ 0 ;  }3  3;

( d(d )  minn{d (d );d )(vd  (vc ,dv )}  mmin{  0;  }  ;

( d(w )  minn{d (w );d )(vd  (vc ,wv )}  mmin{  0;  }  .

Осскільки ввеличинна d(c)=33 є мініммальноюю з величчин d(x)), то

позначааємо верршину cc. Так саамо познначаємо і дугу (v, c), яяка і

визначаає величину dd(с). Пррисвоюєммо у=с. Поточчне деррево

найкороотших шшляхів сккладайсяя з дуги (v, c) (риис. 4.4, аа).

а б в

г г д

Рисуунок 4.44. Наросттаюче оррієнтоваане деревво найкооротшихх

шшляхів

46