Page 85 - 4496

виходить з вершини з меншим номером у вершину з більшим
номером і при цьому можлива послідовна нумерація вершин
від 1 до n=|A|.
Будемо використовувати широко розповсюджений у
програмуванні прийоми для скорочення розв'язку
комбінаторних завдань - спочатку витрачаються додаткові
зусилля на попереднє впорядкування, потім в упорядкованій
множині більш просто знаходять розв'язок.
1. Упорядкуємо множину вершин так, щоб будь-яка
дуга виходила з вершини з меншим номером і заходила у
вершину з більшим номером. Це можна зробити так:
привласнимо початковій вершині номер 1. Усім вершинам A',
пов'язаним з початковою по вихідних дугах, зіставимо номера
від 2 до А'. Після цього перевіримо номери цих вершин на
виконання умови. Для будь-якої пари вершин, де умова не
виконується, переставимо номери вершин. Потім
розглядаються вершини, пов'язані по вихідних дугах з
множиною А' і т.д.
2. Привласнимо всім вершинам ваги l(i)=0.
3. Послідовно для вершин 1, 2, 3, ... проведемо
перерахування ваг за формулою

l(i) = max (l(i), l(j)+C ji ),

де максимум береться по всіх вершинах j, з яких є дуги у
вершину i. Це можна зробити, так як ваги всіх вершин j
обчислені раніше, тому що i>j. Скорочення обчислювальних
витрат у порівнянні з алгоритмом Дейкстри пов'язане з тим,
що відпадає необхідність на кожному кроці визначати чергову
вершину з мінімальною вагою для продовження розрахунків.
4. Як і в алгоритмі Дейкстри, виділимо зворотним
ходом шуканий шлях.
Приклад. Нехай вихідний граф має вигляд рис. 3.13. На
рисунку показана ситуація після виконання першого кроку,
коли зроблена перенумерація вершин. У табл. 3.2 зазначені
ваги вершин після виконання другого й третього кроків
алгоритму.

82