Зважені графи

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

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

У різних застосуваннях вага може набувати додатних чи від’ємних, цілих чи дробових значень. У деяких застосуваннях розглядаються графи з кількома вагами кожної дуги; наприклад, у сітковій транспортній задачі кожній дузі можуть відповідати дві ваги — довжина дуги і її пропускна здатність.

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

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

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

Нехай у зв’язному орієнтованому чи неорієнтованому зваженому графі без кратних дуг (ребер) і петель з n вершинами , , …, і невід’ємними вагами треба знайти найкоротший шлях (ланцюг) із вершини у деяку вершину ( ).

Найефективнішим алгоритмом знаходження найкоротшого шляху (ланцюг) від однієї вершини до іншої, якщо вага кожного ребра (дуги) додатна, є алгоритм Дейкстри³.

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

Алгоритм Дейкстри передбачає таку послідовність кроків.

К1. Присвоюємо початкові значення і розставляємо позначки: і вважаємо позначку 0 вершини постійною, тому останньою позначеною вершиною є ; також записуємо відповідну інформацію в таблицю; ( ) і вважаємо позначки вершин тимчасовими.

К2. Оновлюємо позначки: для кожної вершини з тимчасовою позначкою, в яку з вершини р іде дуга (ребро) , позначку замінюємо позначкою:

.

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

К4. Якщо остання помічена постійною позначкою вершина р є вершиною , то — довжина найкоротшого шляху (ланцюга) із вершини у вершину , а найкоротший шлях (ланцюг) легко записати, проходячи з кінця таблиці і враховуючи відповідні суміжні вершини; інакше — переходимо на К2.

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

Щоб знайти найкоротші шляхи (ланцюги) від до всіх решти вершин ( ) графа G, то наведений алгоритм треба виконувати доти, поки всі вершини не одержать постійних позначок.

Приклад. Дано зважений зв’язний орієнтований граф:

Знайти найкоротший шлях від вершини а до вершини g.

Розв’язання. Маємо орієнтований граф без петель і кратних ребер з додатними вагами. Тому можна застосувати алгоритм Дейкстри для знаходження найкоротшого шляху.

К1 — присвоюємо початкові значення і розставляємо позначки: і вважаємо позначку 0 вершини а постійною, , а також записуємо відповідну інформацію в таблицю:

і біля вершин ставимо позначки:

К2 — з вершини ідуть дуги і і тому попередні позначки біля вершин b і e замінюємо позначками:

;

;

К3 — тимчасові позначки мають вершини b, c, d, e, f, g. Найменшим значенням їхніх позначок є:

.

Тому позначку вершини е робимо постійною:

Останньою позначеною (постійною позначкою) вершиною стає . Відповідні дані вносимо в таблицю:

К2 — з вершини ідуть дуги і і тому попередні позначки біля вершин d і f замінюємо позначками:

;

;

К3 — тимчасові позначки мають вершини b, c, d, f, g. Найменшим значенням їхніх позначок є:

Тому позначку вершини b робимо постійною:

Останньою позначеною (постійною позначкою) вершиною стає . Відповідні дані вносимо в таблицю:

К2 — з вершини ідуть дуги , і ; перерахуємо значення позначок:

;

;

.

Тому попередню позначку біля вершини с замінюємо на 5, позначку 8 біля вершини f замінюємо на 7, а позначку 6 біля вершини d не замінюємо:

К3 — тимчасові позначки мають вершини c, d, f, g. Найменшим значенням їхніх позначок є:

Тому позначку вершини с робимо постійною:

Останньою позначеною (постійною позначкою) вершиною стає . Відповідні дані вносимо в таблицю:

К2 — з вершини виходить одна дуга ; перерахуємо значення позначки вершини f:

.

Оскільки значення позначки вершини d не змінилося, то на графі ніякі зміни не відобразяться.

К3 — тимчасові позначки мають вершини d, f, g. Найменшим значенням їхніх позначок є:

.

Тому позначку вершини d робимо постійною:

Останньою позначеною (постійною позначкою) вершиною стає . Позначки 6 вершина d набула при підході до неї з вершини е і з вершини с, тому в таблицю як попередню суміжну до d вершину можна внести або с, або е; внесемо, наприклад, е:

К2 — з вершини ідуть дуги і ; перерахуємо значення позначок:

.

;

Тому попередню позначку біля вершини g замінюємо на 9, а позначку 7 біля вершини f не замінюємо:

К3 — тимчасові позначки мають дві вершини f і g. Менше значення позначки має вершина f:

Тому позначку вершини f робимо постійною:

Останньою позначеною (постійною позначкою) вершиною стає . Позначки 7 вершина f набула при підході до неї з вершини b; у таблицю внесемо відповідну інформацію:

К2 — з вершини виходить одна дуга ; перерахуємо значення позначки біля вершини g:

.

Попередню позначку 9 біля вершини g замінюємо на 8:

К 3 — тимчасову позначку має лише вершина g. Тому останньою позначеною (постійною позначкою) вершиною стає вершина :

У таблицю внесемо відповідну інформацію:

К4 — оскільки , то — довжина найкоротшого шляху із вершини а в вершину g. Найкоротший шлях одержимо за таблицею, починаючи з її кінця:

Отже, найкоротшим шляхом із вершини а в вершину g є шлях: , який має довжину 8.

Оскільки в даному прикладі всі вершини помічено постійними позначками, то, користуючись таблицею, можна знайти шляхи із вершини а в будь-яку іншу вершину: (має довжину 4), (5), (6; знайдений шлях не єдиний мінімальний — таку ж довжину має шлях ), (2), (7).