Page 68 - 4336

Таким чином, у тих випадках, коли немає можливості

скористатися найкращим розв'язком, можна знайти йому заміну

із числа додаткових розв'язків. Крім того, знання розв'язків,

найближчих до найкращого, дозволить визначити стійкість

системи стосовно зовнішніх факторів, вплив яких не

враховується в моделі транспортної мережі.

У даному підрозділі описується алгоритм подвійного

пошуку (double-sweep), який знаходить k перших найкоротших

шляхів з деякої фіксованої вершини до усіх інших вершин

вхідного графа.

Алгоритми Дейкстри, Флойда-Уоршола та Данцига, що

наведені вище, дозволяють знаходити тільки найкоротші шляхи

між вершинами. Ці алгоритми включають в основному операції

додавання та порівняння, які виконуються над звичайними

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

Зокрема, використання в алгоритмі Дейкстри співвідношення

(4.1) пов'язане з виконанням лише операцій додавання та

порівняння. Те ж саме відноситься і до використання в алгоритмі

Флойда-Уоршола співвідношення (4.2), а в алгоритмі Данцига –

співвідношень (4.5)-(4.8).

Алгоритм подвійного пошуку також складається винятково

з операцій додавання та порівняння. Однак ці операції

виконуються не над числами, як в попередніх алгоритмах, а над

наборами з k чисел (векторами), що представляють довжини

k
відповідних дуг або шляхів. Враховуючи це, введемо множину R
векторів (d , d , ..., d ), що задовольняють умову d <d <...<d . Дані
1
k
2
k
1
2
вектори повинні мати однакову розмірність і можуть містити як
скінченні, так і нескінченні елементи. Однак, необхідно, щоб
скінченні елементи передували нескінченним і були розташовані

68