бовий пасажиропотік q-тої струменя;
На розгалуженому напрямку допускаються різні маршрути проходження пасажирів між вузлами, тому спочатку необхідно провести розподіл кореспонденцій пасажиропотоків між вузлами полігону, яке зводиться до пошуку найкоротших за часу проходження шляхів між ними.
Метод вибору маршруту проходження пасажирів з використанням алгоритму пошуку найкоротших шляхів між будь-якими двома вузлами полігону заснований на застосуванні тернарной операції і дозволяє отримати матрицю довжин найкоротших шляхів.
Сутність тернарной операції полягає в наступному:
d ik = d ij + d jk , якщо d jk > d ij + d ik і i В№ j В№ k, (2.15)
Де d ik - довжина деякого шляху, з'єднує i-й і k-й вузли;
d ij , d jk - довжини шляхів, що з'єднують відповідно i-й і j-й; та j-й і k-й вузли;
Розрахунок починається з побудови вихідної матриці Д1, в якій елемент d jk дорівнює довжині дуги (i, k), якщо така дуга належить напрямку G, тобто (I, k) ГЋG і d jk = ВҐ в іншому випадку. Одночасно будується матриця В1 з елементами (i, k), рівними k. p> Перерахунок елементів матриці Д1 відповідно до тернарной операцією викликає перерахунок елементів матриці В1 за наступним правилом:
(i, j), якщо d jk > d ij + d ik (2.17)
(i, k) = (i, k), якщо d jk ВЈ d ij + d ik (2.18)
Робота алгоритму починається з застосування тернарной операції при j = 1, тобто перерахунку всіх елементів матриць Д1 і В1, крім елементів першого рядка і першого стовпця. Всі інші елементи матриці Д1 залишаються без зміни. У результаті виходять матриці Д2 і В2. Наступна ітерація зводиться до перерахунку всіх елементів матриць Д2 і В2, крім елементів другого стовпця і другого рядка, тобто при j = 2. Продовжуючи аналогічні обчислення, отримують інші матриці. p> Остання матриця - Матриця довжин найкоротших шляхів між вузлами напряму. По ній можна визначити послідовність вузлів і побудувати будь-який з найкоротших шляхів між ними. p> Вихідні матриці Д1 і В1:
Матриця Д1
I/k
1
2
3
4
5
6
1
0
977
ВҐ
ВҐ
ВҐ
ВҐ
2
977
0
ВҐ
ВҐ
ВҐ
ВҐ
3
ВҐ
ВҐ
0
ВҐ
ВҐ
ВҐ
4
ВҐ
ВҐ
ВҐ
0
ВҐ
ВҐ
5
ВҐ
ВҐ
ВҐ
595
0
ВҐ
6
ВҐ
ВҐ
ВҐ
552
ВҐ
0
Матриця В1
I/k
1
2
3
4
5
6
1
1
2
3
4
5
6
2
1
2
3
4
5
6
3
1
2
3
4
<...
