Page 53 - 4387

називаються відповідно верхньою трикутною та нижньою

0
трикутною підматрицями матриці (рис. 7.1).

d 0 1 , 1 d 0 2 , 1 d 0 3 , 1 V V V V d 0 2 , 1 d 0 3 , 1
0
D = d 0 1 , 2 d 0 2 , 2 d 0 3 , 2 , L = d 0 1 , 2 V V , U = V V d 0 3 , 2 .

d 0 1 , 3 d 0 2 , 3 d 0 3 , 3 d 0 1 , 3 d 0 2 , 3 V V V V

Рисунок 7.1.

Якщо необхідно визначити довжини k найкоротших шляхів,

що ведуть із деякої фіксованої вершини (наприклад, вершини 1) у

кожну вершину вхідного графа, то слід визначити тільки перший

∗ ∗ ∗ ) матриці . Зазначимо, що цей рядок
∗
рядок ( , , …, 1,
1,1
1,2
k
складається з N векторів, що належать R . Отже, необхідно
визначити Nk величин і Nk шляхів, що мають відповідні довжини.
Алгоритм подвійного пошуку дозволяє ефективно

знаходити зазначені Nk шляхів. При цьому, вимагається, щоб у

вхідному графі були відсутні контури від'ємної довжини.

Робота алгоритму подвійного пошуку починається з

0 0 0 ), що поелементно
формування деякого рядка ( , , …, 1,
1,1
1,2
∗
∗
оцінює зверху оптимальний рядок ( , , …, ∗ ). Це
1,1 1,2 1,
означає, що кожний елемент будь-якого вектора не менший
відповідного елемента вектора . При цьому, в початковій
∗
1,
точці повинно бути 0 = 0. Зокрема, всі елементи оцінюючого
1,1,1
0 , рівного нулю) могли б бути
рядка (за винятком елемента 1,1,1
прийняті рівними ∞. Потім в алгоритмі обчислюються нові
(менші) оцінки для кожного вектора . Це здійснюється
∗
1,
шляхом багаторазового коректування вхідного оцінюючого

вектора . Коректування полягає в переході до нового вектора,
0
1,

52