Page 27 - 4387

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) (рис. 3.2 д).

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

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

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

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

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

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

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

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

3.3 Порядок виконання роботи

Варіант № 1

1. Використовуючи алгоритм Дейкстри, знайти у графі,

наведеному на рис. 3.3 а, найкоротший шлях між вершинами a та
g. Побудувати наростаюче орієнтоване дерево найкоротших

шляхів.

а б

Рисунок 3.3.

26