>
31
[801,21]
Постійна
23
[810,12]
Постійна
22
[933,2]
Постійна
38
[992,31]
Постійна
3
[1108,38]
Постійна
Найкоротшій шлях между Вузли 15 и будь-яким іншім Вузли візначається починаючі з Вузли призначення Шляхом проходження їх у зворотнього Напрямки помощью ІНФОРМАЦІЇ, представленої в постійніх мітках. Найкоротшій маршрут между Вузли 15 и 3 має таку послідовність вузлів: (3) в†’ [1108.38] в†’ (38) в†’ [992.31] в†’ (31) в†’ [801.21] в†’ (21) в†’ (15). p> Таким чином, одержуємо шлях загальною Довжина 1108 км.
4. Завдання для найбільш Потік (алгоритм Форда-Фалкерсона)
Рішення задачі Складається з підготовчого етапу и кінцевого числа кроків, на кожнім з якіх відбувається Припустиме Збільшення потоку. На підготовчому етапі формується матриця пропускних здатностей дуг мережі.
Таблиця 4.1. Матриця пропускних здатностей дуг мережі
В
15
12
2
21
31
23
22
38
3
15
-
10
10
10 -
12
7
-
7
7
7
2
13
13
-
13
13
В
13
21
18 +
18
-
18 -
31
22
22 +
-
22
22 -
23
22
В
-
22
22
22
22
21
21
21
21
-
21
21
38
28 +
28
28
-
28 -
3
7
