аписані нижче в таблицю 2.
Таблиця 2
Вузол мережі
Найкоротший маршрут
В
топологія
протяжність
2
1-2
5
3
1-2-3
9
4
1-2-3-4 або 1-4
11
5
1-2-3-4-5 або 1-4-5
14
6
1-2-3-4-5-6 або 1-4-5-6
22
7
1-2-3-4-5-6-7 або 1-4-5-6-7
25
Приклад:
Транспортна компанія вибирає маршрут з пункту 1 до пункту 7 для доставки товару і бажає скоротити час у дорозі свого автотранспорту. Час необхідний для перевезення товару по кожній ділянці шляху позначено поряд з кожним ребром мережі. Необхідно прокласти маршрут, забезпечує мінімальний час автотранспорту в дорозі.
За допомогою алгоритму побудови найкоротшого маршруту такий тип завдання можна вирішити. У результаті розрахунків мінімальний час у дорозі становитиме 25 годин. p> 4. Знаходження максимального потоку.
Знайти максимальний потік можна одним з нижчеописаних способів.
В
4.1 Серія послідовних кроків.
На графіках вкажемо ступінь насичення потоку над кожним ребром, а в дужках залишкову пропускну здатність.
Крок 1: побудуємо потік 1-2-3-4-5-6-7 і знайдемо максимальну пропускну здатність цього шляху.
В
Min ( C ij ) = C 34 = 2
О¦ 1 = 2
В В В В В В В
Потік не повний
В В
Крок 2: побудуємо потік 1-4-5-6-7
Min ( C ij ) = C 45 = 1
О¦ 2 = О¦ 1 + 1 = 3
В В В В В В В В
Потік не повний
В В
Крок 3: побудуємо потік 1-4-7
Min ( C ij ) = C 14 = 10
О¦ 3 = О¦ 2 + 10 = 13
В В В В В В В В
О¦
