Page 52 - 4387

то невизначені елементи вектора умовно приймаються
0
,
рівними ∞. Наприклад, якщо вершина i з'єднана з вершиною j

трьома дугами, що мають довжини відповідно 9, 13 і 9, то для k=4

=(9, 13, ∞, ∞). При i=j вважаємо, що існує деяка дуга нульової
0
,
довжини, що є петлею у вершині i. Позначимо через D матрицю,
0
елемент якої збігається з вектором .
0
,
Занумеруємо вершини вихідного графа цілими числами від

k
)∈R , елементи
1 до N. Введемо вектор =( , , …,
, ,,1 ,,2 ,,
якого задають довжини k найкоротших шляхів, що ведуть із

вершини i у вершину j та використовують у якості проміжних

вершини 1, 2, .., m. Позначимо через матрицю, кожний

елемент якої збігається із .

,
k
∗ ∗ ∗ ∗ )∈R вектор,
Позначимо через =( , , …,
, ,,1 ,,2 ,,
елементи якого збігаються з довжинами k найкоротших шляхів,

що ведуть із вершини i у вершину j. Ці довжини будемо називати

оптимальними довжинами відповідних шляхів. Позначимо через

D матрицю, кожний елемент якої збігається із .
∗
∗
,
k
Виберемо із множини R вектори F=(0, ∞, ∞, …, ∞) та
k
V=(∞, ∞, ∞, …, ∞). Тоді, для будь-якого вектора A∈R
справедливі наступні співвідношення:

A⊕ V = A, (7.3)

A⊗ V = V , (7.4)

A⊗ F = A (7.5)

Нехай матриця L утворена з матриці шляхом заміни всіх
0
елементів кожного вектора (при i≤j) величиною ∞. Нехай
0
,
матриця U утворена з матриці шляхом заміни всіх елементів
0

кожного вектора (при i≥j) величиною ∞. Матриці L і U
0
,
51