Page 83 - 4496
P. 83
вершина. У результаті безліч віднесених до шляху дуг дадуть
шуканий розв'язок.
Приклад. Задано граф наведений на рис. 3.12 Хід
розв'язку представимо таблицею 3.1.
Рисунок 3.12 – Граф, для якого необхідно знайти най
Виконуючи крок 4 алгоритму, виділимо шлях 12-9-6-3-
2-1. Але існує ще один шлях тієї ж довжини-12-9-8-5-4-1, тому
що для вершини 9 маємо два однакові по довжині шляхи до
початку, що проходять через вершини 8 і 6.
Легко бачити, що розв'язком завдання по алгоритму
Дейкстри завжди буде шлях мінімальної довжини.
Таблиця 3.1 – Знаходження найкоротшого шляху
р ai Вага
1 2 2
4 3
2 3 5
5 7
4 5 6
7 7
3 6 6
80
