Page 62 - 4387

табл. 7.1. За співвідношенням (7.8) знаходяться і відповідні k-ті

шляхи.

Таблиця 7.1 – Результати роботи алгоритму подвійного

пошуку

r Тип пошуку Вектор оцінок

1
Зворотній d 1 = , 0 ( ∞ ,∞ ) (∞ ,∞ ,∞ ) (∞ ,∞ ,∞ ) (∞ ,∞ ,∞ )
r=0
Прямий d 1 2 = , 0 ( ∞ ,∞ ) , 1 ( ∞ ,∞ ) , 0 ( ∞ ,∞ ) (− , 1 ∞ ,∞ )

Зворотній d 1 3 = ) 3 , 2 , 0 ( , 2 , 1 ( ∞ ) , 1 , 0 ( ∞ ) (− , 1 ∞ ,∞ )

r=1
Прямий d 1 4 = ) 3 , 2 , 0 ( ) 3 , 2 , 1 ( ) 2 , 1 , 0 ( (− ) 1 , 0 , 1

r=2 Зворотній d 1 5 = ) 3 , 2 , 0 ( ) 3 , 2 , 1 ( ) 2 , 1 , 0 ( (− ) 1 , 0 , 1

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

Варіант № 1

1. Використовуючи алгоритм подвійного пошуку, знайти
перші два найкоротші шляхи, що ведуть з вершини 1 у всі інші

вершини графа, наведеного на рис. 7.3 а.

а б

Рисунок 7.3.

61