Тимчасовий статус мітки [992,31] вузла 38 заміняється на постійний (U38=992).
Крок 8. З вузла 38 можна досягти вузла 3. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
2
[237,15]
21
[512,15]
31
[801,21]
23
[810,12]
22
[933,2]
38
[992,31]
3
[1855,23]
Тимчасова
[992+116,38]= [1108,38]
На останньому кроці знайдено найкоротшу відстань для вузла 3 – [1108.38]. Таким чином статус мітки вузла 3 змінюється на постійний.
Кінцевий результат міток має такий вигляд:
[1108,38]
Найкоротший шлях між вузлом 15 і будь-яким іншим вузлом визначається починаючи з вузла призначення шляхом проходження їх у зворотному напрямку за допомогою інформації, представленої в постійних мітках. Найкоротший маршрут між вузлами 15 і 3 має таку послідовність вузлів: (3)→ [1108.38] →(38)→ [992.31] →(31)→ [801.21] →(21)→ (15).
Таким чином, одержуємо шлях загальною довжиною 1108 км.
4. Задача про максимальний потік (алгоритм Форда-Фалкерсона)
Рішення задачі складається з підготовчого етапу і кінцевого числа кроків, на кожнім з яких відбувається припустиме збільшення потоку. На підготовчому етапі формується матриця пропускних здатностей дуг мережі.
Таблиця 4.1. Матриця пропускних здатностей дуг мережі
-
10
10-
7
13
18+
18
18-
22+
22-
28+
28
28-
7+
По табл. 4.1. знаходимо шлях l1=(15,21,31,38) зі станції 15 у 3 з позитивною пропускною здатністю. Елементи цього шляху позначаємо знаком «мінус», а симетричні – знаком «плюс». Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг: C1= min {10,18,22,28}=10.
Визначаються залишкові пропускні здатності дуг знайденого шляху і симетричних йому дуг. Для цього з елементів табл. 4.1. віднімаємо , а до елементів додаємо . У результаті одержимо нову табл. 4.2 зі зміненими пропускними здатностями.
Таблиця 4.2. Матриця пропускних здатностей дуг мережі
0
13+
13-
8
32
21+
21-
17
Страницы: 1, 2, 3, 4, 5
