7 Найкоротші ланцюги і потоки мінімальної вартості

7.1 Найкоротші ланцюги

Допустимо, що є мережа, у якій кожній дузі поставлена у відповідність довжина, або віддаль . Довжиною ланцюга називається сума довжин , яка взята за всіма дугами цього ланцюга. Необхідно знайти ланцюг мінімальної довжини із заданого вузла у заданий вузол . Будемо вважати, що . Якщо деяка пара вузлів і не зв’язана безпосередньо дугою, то вважаємо . Відмітимо, що величини не обов’язково повинні задовольняти умові симетричності .

Будемо замість знаходження найкоротшого шляху із в шукати найкоротші ланцюги із в усі інші вузли мережі. Це пояснюється тим, що будь-який вузол може виявитись деяким проміжним вузлом найкоротшого шляху із в . Якщо вузол належить найкоротшому шляху із в , то його частина із в повинна бути найкоротшою. Дійсно, в протилежному випадку вказану частину ланцюга із в можна було б замінити на найкоротшу, і при цьому вийшов би коротший ланцюг із в . Але це б входило у протиріччя з тим фактом, що початковий ланцюг із в – найкоротший.

Розглянемо дуги, які входять у найкоротші ланцюги із у всі інші вузли ; ці дуги утворюють деякий граф. Спробуємо вилучити із цього графа як можна більше дуг так, щоби при цьому залишилось по одному ланцюгу із у кожний вузол . (Якщо існує тільки один найкоротший ланцюг із вузла у вузол , то уже неможливо вилучити жодної дуги). Якщо, наприклад, є два найкоротші ланцюги із у , то якась дуга в одному із цих ланцюгів може бути вилучена, а саме остання дуга ланцюга або . Після вилучення таких «лишніх» дуг залишиться граф, який буде деревом. Таким чином, якщо деяка дуга належить цьому дереву, то найкоротшим ланцюгом із у буде сама дуга . Алгоритм, що розглядається нижче, дає можливість отримати таке дерево.

Отже, необхідно побудувати дерево, яке складається із найкоротших ланцюгів із до всіх інших вузлів мережі. Дуги, які належать цьому дереву будемо називати, дугами дерева, а дуги, що не належать йому – дугами поза деревом. Після того як дерево побудовано, кожний найкоротший ланцюг буде складатись із дуг дерева. На початку алгоритму всі дуги мереж вважаються дугами поза деревом. У процесі роботи алгоритму кількість дуг поступово збільшується від 1 до , де - число вузлів даної мережі.

Робота алгоритму протікає наступним чином: допускаємо, що вузол належить шуканому дереву. Допустимо тепер, що знайдено дуг дерева ( ). Довжину найкоротшої серед таких мереж позначимо як . Якщо всі ланцюги із у вміщують на деякому кроці алгоритму більше однієї дуги поза деревом, то допускаємо . Відмітимо, що величина залежить від : вона змінюється у міру збільшення . Взагалі-то, .

Допустимо, що у процесі роботи алгоритму побудована частина шуканого дерева, яку будемо називати поточним деревом. Вузол , який не належить до поточного дерева, будемо називати сусіднім з цим деревом, якщо у мережі є дуга або дуга , де - деякий вузол поточного дерева. Тоді ланцюг довжини із вузла у вузол вміщує тільки дуги дерева, і відповідно, . Із визначення витікає, що

,

де мінімум береться за всіма вузлами поточного дерева.

На кожному кроці алгоритму число дуг число дуг збільшується на одиницю, при цьому величини повинні бути вирахувані для всіх вузлів, сусідніх із знов побудованим деревом. Для цього наявна величина порівнюється з величиною . Якщо , то параметру присвоюється значення ; якщо ж , то залишається без змін. Символічно це записується наступним чином:

, (7.1)

де символ := позначає оператор присвоювання.

Тепер можна привести увесь алгоритм розв’язку задачі:

Крок 0. Допустити, що вузол належить дереву; ; для сусідніх з вузлів , для інших .

Крок 1. Покласти , де - вузли сусідні з поточним деревом. Дугу включити в число дуг дерева.

Крок 2. Якщо число дуг дорівнює , то кінець. Якщо ні, то перейти до кроку 3.

Крок 3. . Перейти до кроку 1.

Цей алгоритм можна реалізувати шляхом розстановки поміток. Кожний вузол отримує помітку вигляду . Перша частина помітки – це величина або , а друга частина вказує на сусідній з вузол у найкоротшому ланцюгу із у . Помітка називається тимчасовою, якщо вона має вигляд , і постійною, якщо вона має вигляд . Спочатку кожний вузол , який є сусіднім з вузлом , отримує тимчасову помітку . Якщо , то вузол отримує постійну помітку .

Приклад 7.1. Знайти найкоротший ланцюг для мережі, яка показана на рис. 7.1, де числа поруч з дугами означають віддалі. Лінії без стрілок – неорієнтовані дуги; вважаємо, що для неорієнтованих дуг .

Спочатку всі вузли мережі не належать дереву: вузли , , - сусідні з вузлом . Присвоюємо тимчасові помітки: - вузлу , - вузлу , - вузлу . Так як , помітка стає постійною поміткою вузла , а дуга - дугою дерева. Отже, знайдена тільки одна дуга .

Тепер вузлами, які з’єднані з деревом, будуть вузли , , , . Присвоюємо їм тимчасові помітки:

,

,

,

.

Рисунок 7.1 – Мережа разом з поміченими дугами

Найменшою із цих поміток є , отже, вона стає постійною, а дуга - дугою дерева. Тепер поточне дерево складається із двох дуг - і . Продовжуємо обчислення. Сусідніми з деревом будуть вузли , , . Тому

,

,

.

Найменшою із трьох поміток є і вона стає постійною, дуга - дугою дерева. Отже, після двох циклів обчислень поточне дерево буде складатись із трьох дуг: , і . Сусідніми з поточним деревом залишаються вузли і . Для них обчислюємо

,

.

Тепер стає постійною поміткою, а дуга - дугою дерева. Після третього циклу обчислень маємо поточне дерево з дугами - , , і , а сусідніми вузлами будуть - і . Обчислимо

,

.

Отже, стає постійною поміткою, дуга або можуть стати дугами дерева. Виберемо як дугу дерева. Тоді

.

Таким чином, дуга стає дугою дерева і на цьому обчислення закінчуються. На рис 7.1 дуги дерева виділені жирними лініями, а помітки вузлів наведені у дужках.