Page 50 - 4336

2. Якщо ддля деякої поззначеної вершини х ввідбуваєтться

зменшеення велличини dd(x), то із цієї ввершинии та інциидентноої їй

позначееної дугии позначчення зніімаєтьсяя.

3. Процедуура алгооритму ззакінчуєється тілльки тодді, коли усі

вершинни познаачені та коли ппісля викконанняя кроку 2 жоднне із

чисел dd(x) не зммінюєтьсся.

Прриклад 4.3. Виикористоовуючи алгориттм Белммана-Форрда,

знайти у графі, зображженому нна рис. 44.6, найккоротшийй шлях між

вершиннами a таа е.

Рисуунок 4.6.

Роозв'язок.

Кррок 1. ППозначааємо верршину a. Вважжаємо, що d(a)=0,

d(x)=∞, для всіхх вершинн х, які нне збігаюються з aa. Присвоюємо уу=a.

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

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

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

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

( d(d )  minn{d (d );d(ad )  (ac ,da )}  mmin{  0;  }   ;

 }
( d )(e  minn{d (e ); ( d(a )  (ac ,ea )}  mmin{  0;    .
Осскільки ввеличинна d(b)=33 є мініммальноюю з величчин d(x)), то

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

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

найкороотших шшляхів сккладайсяя з дуги (a, b) (риис. 4.7, аа).

50