Page 48 - 4336

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

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

d (b )  min{d (b ); d (d )  c (d ,b )}  min{ 6 ; 7   }  7 ;

d (w )  min{d (w );d (d )  c (d ,w )}  min{ 6 ;  } 2  8.

Оскільки величина d(b)=7 менша за величину d(w), то

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

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

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

(рис. 4.4, г).

Крок 3. Оскільки вершина w залишається непозначеною,

переходимо до кроку 2.

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

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

d (w )  min{d (w ); d (b )  c (b , w )}  min{ 7 ; 8  } 2  8.

Отже, позначаємо вершину w. Разом з нею позначаємо і

дугу (d, w), що визначає величину d(w). Остаточно побудоване

дерево найкоротші шляхів складається з дуг (v, c), (v, а), (с, d),

(v, b) та (d, w) (рис. 4.4, д).

Найкоротший шлях, що з'єднує вершину v з вершиною w,

складається з дуг (v, c), (с, d) та (d, w) і має довжину 3+3+2=8. Це

не єдиний найкоротший шлях між вершинами v та w. Шлях, що

складається з дуг (v, а), (а, d) та (d, w), має довжину 4+2+2=8 і

також є найкоротшим шляхом між вершинами v та w.

Найкоротший шлях буде єдиним тільки у тому випадку, якщо в

процедурі алгоритму жодного разу не виникає неоднозначність у

виборі дуги, що позначається.

48