3.3. Пошук найкоротших відстаней та шляхів у зважених графах.

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

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

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

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

В цьому підрозділі розглянемо дві відомі та важливі задачі, що пов’язані з пошуком оптимальних шляхів у зважених графах.

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

Алгоритм 3.4. (Краскала) Побудова остова мінімальної ваги.

Спочатку множина обраних ребер є порожньою.

Крок 1. Сортуємо ребра графа за зростанням ваги.

Крок 2. Поки це можливо, виконуємо таку операцію: додаємо до множини ребро найменшої ваги, що не утворює цикл з ребрами, які обрали раніше.

Якщо крок 2 виконати неможливо, то алгоритм закінчує свою роботу. ■

Зауважимо, що розгляд алгоритмів сортування масивів виходить за межі даного посібника. Існує досить значна кількість (не менше десяти) різноманітних алгоритмів сортування масивів, з яких можна виділити алгоритм Хоара (так званий алгоритм QuickSort), сортування злиттям, метод Шелла та багато інших. Опис та порівняння алгоритмів сортування масивів можна знайти зокрема в [Кормен, Ахо] та багатьох інших джерелах.

Розглянемо докладніше ситуацію, що виникає при виконанні кроку 2. Оскільки обирати ребра, що утворюють цикл з обраними раніше, заборонено, то потрібно не допустити вибір такого ребра. Найбільш простим способом дослідження, чи можна обирати поточне ребро, є знаходження компонент зв’язності підграфа після кожного вибору ребра. Нехай поточним за зростанням ваги є ребро . Можливий один із таких випадків:

а) Обидві вершини не належали жодній компоненті зв’язності. Тоді додаємо нову компоненту, що складається з вершин та.

б) Одна вершина (нехай, для визначеності, вершина ) належала деякій компоненті зв’язності, а інша не належала жодній компоненті. Тоді вершинадодаємо до компоненти, що містить вершину.

в) Одна вершина належала одній компоненті зв’язності, а друга – іншій. Тоді ці дві компоненти зв’язності об’єднуємо в одну.

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

В результаті виконання алгоритму Краскала ми одержимо всі вершини графа в одній компоненті. Процес послідовного вибору ребер доцільно розглядати у вигляді таблиці, в якій вказуємо обране ребро, компоненти зв’язності підграфа, що складається з обраних ребер та вагу цього підграфа.

Проілюструємо виконання цього алгоритму на наступному прикладі.

Приклад 3.7. Зважений граф , у якогозадано матрицею ваг:

За допомогою алгоритму Краскала знайти для цього графа остів мінімальної ваги.

Хід виконання алгоритму Краскала відобразимо у таблиці 3.1.

Обране ребро	Компоненти зв’язності	Вага обраного фрагменту
		1
		2
	,	4
	, ,	7
	,	11
		16

Таб. 3.1. Ілюстрація виконання алгоритму Краскала для графа з прикладу 3.7.

На рисунку 3.13 побудуємо діаграму знайденого остову:

Рис. 3.13. Остів найменшої ваги для графа з приклада 3.7.

■

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

Алгоритм 3.5. (Прима) Побудова остова мінімальної ваги.

Спочатку множина обраних ребер та множина обраних вершинє порожніми.

Крок 1. Сортуємо ребра графа за зростанням ваги.

Крок 2. Обираємо ребро найменшої ваги. Вершинитадодаємо до множини обраних вершин.

Крок 3. Поки це можливо, виконуємо такі операції: додаємо до множини ребро найменшої ваги вигляду, детаі додаємо вершинудо множини обраних вершин.

Якщо крок 3 виконати неможливо, то алгоритм закінчує свою роботу. ■

Хід виконання алгоритму Прима зручно зображати у вигляді таблиці, що є аналогічною таблиці для алгоритму Краскала.

Проілюструємо виконання алгоритму Прима.

Приклад 3.8. Для графа з прикладу 3.7 знайти остів мінімальної ваги із використанням алгоритму Прима.

В таблиці 3.2 зобразимо хід виконання алгоритму Прима.

Обране ребро	Компонента зв’язності	Вага обраного фрагменту
		1
		2
		7
		9
		13
		16

Таб. 3.2. Ілюстрація виконання алгоритму Прима для графа з прикладу 3.7.

Остів, що знайдено за алгоритмом Прима збігається з остовом, що знайдено за алгоритмом Краскала (рис. 3.13). ■

Зробимо порівняльний аналіз алгоритмів Краскала і Прима:

а) згідно із загальним кроком алгоритму Прима (кроком 3) в будь-який момент його виконання ми маємо одну компоненту зв’язності, в той час як при виконанні алгоритму Краскала ми можемо мати декілька компонент зв’язності;

б) остови, що знайдені за цими алгоритмами для одного і того ж графа можуть відрізнятися, проте вага цих остовів завжди однакова;

в) алгоритм Прима є дещо складнішим за виконанням, оскільки список ребер, з яких треба знаходити ребро мінімальної ваги при кожному виконанні кроку 3 постійно оновлюється;

г) алгоритм Прима є більш використаним у практиці, оскільки при поступовій побудові мережі її незв’язні частини або приводять до незручностей, або взагалі неприпустимі.

Розглянемо ще одну важливу та корисну задачу, що пов’язана із зваженими графами.

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

Спочатку розглянемо найбільш вживаний частинний випадок, коли всі ваги є невід’ємними. Для цієї задачі найбільш відомим алгоритмом розв’язку є алгоритм Дейкстри. Ідея цього алгоритму полягає в тому, що спочатку кожній вершині, відмінній від вершини 1, виставляємо відстань, що дорівнює , а далі покроково ці відстані зменшуємо, поки не знайдемо мінімальну відстань та найкоротший шляхдля кожної вершини. Запишемо кроки алгоритму Дейкстри.

Алгоритм 3.6. (Дейкстри) Відшукання найкоротших відстаней та шляхів від однієї вершини графа до усіх інших для зваженого графа з невід’ємними вагами.

Спочатку всі вершини є непоміченими, відстань до вершини 1 дорівнює 0, до всіх інших вершин відстані дорівнюють , а шляхи є порожніми.

Крок 1. Знаходимо непомічену вершину з найменшою відстанню та помічаємо цю вершину.

Крок 2. Перераховуємо відстані до усіх інших непомічених вершин за формулою. Якщо при перерахуванні відстань до вершинизмінилась, тобто її нова відстань дорівнює сумі відстані до вершинита ваги ребра, то також змінюється шлях до вершини:(під знаком + розуміємо дописування до шляхувершини). Після перерахування повертаємося до кроку 1.

Алгоритм закінчує свою роботу у випадку, коли всі вершини є поміченими, тобто крок 1 виконати неможливо. ■

Хід виконання алгоритму Дейкстри зручно ілюструвати у вигляді таблиці, в якій для кожної вершини відмічаємо її поточну відстань та шлях до неї. Окремо будемо також позначати номер поточної поміченої вершини. Для більш економного запису у таблиці не будемо вказувати відстань (0) і шлях до вершини 1 та початкову відстань до усіх інших вершин (). При перерахуванні відстаней за кроком 2 алгоритму Дейкстри в таблицю будемо вносити зміни лише у випадку покращення відстані. Після завершення виконання алгоритму найкоротші відстані та шляхи для кожної вершини у відповідній колонці будуть записані останніми. Знайдені найкоротші шляхи доцільно зобразити у вигляді дерева.

Проілюструємо хід виконання алгоритму Дейкстри на наступному прикладі.

Приклад 3.9. Зважений граф , у якогозадано матрицею ваг:

За допомогою алгоритму Дейкстри знайти для цього графа найкоротші відстані та шляхи від вершини 1 до усіх інших вершин.

Хід виконання алгоритму Дейкстри відобразимо у таблиці 3.3.

2	3	4	5	6	7	8	9
2	5 4	3	4	7 6 5	8 6 5	6 5	8 7 6
1,2	1,3 1,2,3	1,4	1,2,5	1,6 1,2,6 1,4,6	1,2,7 1,4,7 1,2,3,7	1,8 1,4,8	1,9 1,2,5,9 1,4,6,9

Таб. 3.3. Ілюстрація виконання алгоритму Дейкстри для графа з прикладу 3.9.

При виконанні алгоритму Дейкстри поточними були вершини у такому порядку: 2, 4, 3, 5, 6, 7, 8, 9. Таким чином, найкоротша відстань до вершини 2 дорівнює 2, ,,,,,,. Найкоротшим до вершини 2 є шлях1,2; ;; ;;;;. На рисунку 3.14 зобразимо ці найкоротші шляхи у вигляді дерева.

Рис. 3.14. Найкоротші шляхи (від вершини 1) для графа з приклада 3.9.

■

Розглянемо тепер загальний випадок, коли ваги дуг можуть бути від’ємними. Для існування найкоротших відстаней та шляхів зв’язності графа недостатньо, що ми проілюструємо на наступному прикладі (рис. 3.15).

Рис. 3.15. Зважений граф, у якому не існує найкоротшого шляху від вершини 1.

Спробуємо знайти найкоротшу відстань у цьому графі від вершини 1 до вершини 5. За шляхом 1,2,5 ця відстань дорівнює 8, за шляхом 1,2,3,4,2,5 відстань дорівнює 7, за шляхом 1,2,3,4,2,3,4,2,5 – дорівнює 6 і т.д. Таким чином, завдяки багаторазовому проходженню за циклом (2,3,4,2) для будь-якого цілого числа можна знайти шлях від вершини 1 до вершини 5, довжина якого дорівнює . Тому найкоротшого шляху від вершини 1 до вершини 5 (а також і до усіх інших вершин) не існує. В теорії графів орієнтовний цикл, сума ваг ребер якого є від’ємним числом, дістав назвувід’ємного контуру. Доведено, що у зваженому графі існують найкоротші відстані та шляхи тоді і лише тоді, коли граф є зв’язним та не містить жодного від’ємного контуру.

Для цієї задачі найбільш відомим алгоритмом розв’язку є алгоритм Форда –Белмана. Цей алгоритм є дуже схожим на алгоритм Дейкстри та відрізняється від нього лише двома моментами:

а) оскільки в графі можуть бути ребра від’ємної ваги, то треба перераховувати відстані до усіх вершин, в тому числі до вершин, які було помічено раніше. До таких вершин також може бути зменшення відстані.

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

Запишемо кроки алгоритму Форда – Белмана.

Алгоритм 3.7. (Форда – Белмана) Відшукання найкоротших відстаней та шляхів від однієї вершини графа до усіх інших.

Спочатку всі вершини є непоміченими, відстань до вершини 1 дорівнює 0, до всіх інших вершин відстані дорівнюють , а шляхи є порожніми.

Крок 1. Знаходимо непомічену вершину з найменшою відстанню та помічаємо цю вершину.

Крок 2. Перераховуємо відстані до усіх інших вершин за формулою. Якщо при перерахуванні відстань до вершинизмінилась, то також змінюється шлях до вершини:(під знаком + розуміємо дописування до шляхувершини). Якщо змінюється відстань до раніше поміченої вершини, то помітка цієї вершини знімається. Після перерахування повертаємося до кроку 1.

Алгоритм закінчує свою роботу у випадку, коли всі вершини є поміченими, та крок 2 не приводить до жодної зміни. ■

Хід виконання алгоритму Форда – Белмана зручно ілюструвати у вигляді таблиці. Ця таблиця повністю аналогічна таблиці, що ілюструє виконання алгоритму Дейкстри. Проілюструємо хід виконання алгоритму Форда – Белмана на наступному прикладі.

Приклад 3.10. Зважений граф , у якогозадано матрицею ваг:

За допомогою алгоритму Форда – Белмана знайти для цього графа найкоротші відстані та шляхи від вершини 1 до усіх інших вершин.

2	3	4	5	6	7	8	9
11 10 9	6	12 10	9 8 7	8 7	10 9 8	10	8
1,2 1,3,6,2 1,3,9,2	1,3	1,3,6,4 1,3,9,4	1,5 1,3,5 1,3,9,2,5	1,6 1,3,6	1,3,7 1,3,9,7 1,8,7	1,8	1,3,9

Таб. 3.4. Ілюстрація виконання алгоритму Форда – Белмана для графа з прикладу 3.10.

При виконанні алгоритму Форда – Белмана поточними були вершини у такому порядку: 3, 6, 5, 9, 2, 5, 7, 4, 8, 7. Найкоротші відстані до кожної вершини та шляхи, що їм відповідають, розміщені у відповідному стовпці таблиці останніми. На рисунку 3.16 зобразимо ці найкоротші шляхи у вигляді дерева.

Рис. 3.16. Найкоротші шляхи (від вершини 1) для графа з приклада 3.10.

■