Page 57 - 4387

Після того як будуть знайдені довжини шляхів, виконується

процедура трасування, що дозволяє визначити відповідні шляхи.

Суть її полягає в наступному. Припустимо, що потрібно знайти

m-й найкоротший шлях із початкової вершини в вершину i.

Нехай – довжина цього шляху і нехай вершина j з'єднана
,
дугою з вершиною i. Тоді

d m ,i = d t , j + d ( ) ,i j (7.8)

де – довжина дуги (j, i), – довжина t-гo найкоротшого
, ,
шляху з початкової вершини у вершину j (t≤m). Для кожної

вершини i процедура трасування полягає в пошуку вершини j,

для якої виконується співвідношення (7.8). Як тільки вузол j буде

знайдений, необхідно знову повернутись до даної процедури і

виконувати її доти, поки не буде досягнуто початкової вершини.

Якщо потрібно знайти найкоротші шляхи, що не містять циклів,

то описану вище процедуру слід модифікувати. Модифікація

полягає в наступному: якщо деяка вершина є “кандидатом” у

вершини, що належать розглянутому шляху, то слід перевірити,

чи не була дана вершина раніше одержана за допомогою

співвідношення (7.8).

Приклад 7.2. Використовуючи алгоритм подвійного пошуку,

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

Розв'язок.
Крок 1. Матриця , що складена з дуг даного графа, а
0

також матриці L та U будуть наступними:

56