Зважені графи й алгоритми пошуку найкоротших шляхів

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

Зваженим називають простий граф, кожному ребру е якого приписано дійсне число w(e). Це число називають вагою ребра е. Аналогічно означають зважений орієнтований граф: це такий орієнтований граф, кожній дузі е якого приписано дійсне число w(e) називане вагою дуги. Розглянемо три способи зберігання зваженого графа G = (V, E) в пам’яті комп’ютера. Нехай |V | = n, |E | = m.

Перший – подання графа матрицею ваг W, яка являє собою аналог матриці суміжності. Її елемент w_ij = w(v_i, v_j), якщо ребро {v_i, v_j} є Е (у разі орієнтованого графа дуга (v_i, v_j) є Е). Якщо ж ребро {v_i, v_j}!є Е (або дуга (v_i, v_j)!є Е), то w_ij = 0, чи

W_ij = залежно від розв’язуваної задачі.

Другий спосіб - подання графа списком ребер. Для зваженого графа від кожний елемент списку Е можна відвести три комірки – дві для ребра й одну для його ваги, тобто всього потрібно 3m комірок.

Третій спосіб – подання графа списками суміжності. Для зваженого графа кожний список Adj[u] містить окрім покажчиків на всі вершини v Г(u) ще й числа w(u, v).

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

Задача про найкоротший шлях полягаю в знаходженні найкоротшого шляху від заданої початкової вершини a до заданої вершини z. Наступні дві задачі – безпосередні узагальнення сформульованої задачі про найкоротший шлях.

1. Для заданої початкової вершини a знайти найкоротші шляхи від a до всіх інших вершин.

2. Знайти найкоротші шляхи між усіма парами вершин.

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

Розглянемо два алгоритми: перший алгоритм призначений для розв’язування задачі 1, другий – для задачі 2.

Найефективніший алгоритм визначення довжини найкоротшого шляху від фіксованої вершини до будь-якої іншої запропонував у 1959 р. датський математик Е. Дейкстра (E. Dijkstra). Цей алгоритм застосований лише тоді, коли вага кожного ребра (дуги) додатна. Опишемо докладно цей алгоритм для орієнтованого графа.

Нехай G = (V,E) – зважений орієнтований граф, w(v_i,v_j) – вага дуги (v_i,v_j). Почавши з вершини a, знаходимо віддаль від a до кожної із суміжних з нею вершин. Вибираємо вершину, віддаль якої до вершини a найменша; нехай це буде вершина v* вздовж шляху, який проходить через вершину v*. Якщо для якоїсь із таких вершин ця віддаль менша від поточної, то заміняємо нею поточну віддаль. Знову вибираємо вершину, найближчу до a й не вибрану раніше; повторюємо процес.

Описаний процес зручно виконувати за допомогою присвоювання вершинам міток. Є мітки двох типів – тимчасові та постійні. Вершини з постійними мітками групують у множину М, яку називають множиною позначених вершин. Решта вершин має тимчасові мітки, і множину таких вершин позначимо як T, T = V\M. Позначатимемо мітку (тимчасову чи постійну) вершини v як l(v). Значення постійної мітки l(v) дорівнює довжині найкоротшого шляху, який проходить лише через вершини з постійними мітками.

Фіксованою початковою вершиною вважаємо вершину a; довжину найкоротшого шляху шукаємо до вершини z (або до всіх вершин графа).

Тепер формально опишемо алгоритм Дейкстри.

Алгоритм Дейкстри

Наведемо кроки алгоритму.

Крок 1. Присвоювання початкових значень. Виконати l(a):=0 та вважати цю мітку постійною. Виконати l(v):= для всіх v!=a вважати ці мітки тимчасовими. Виконати x:=a, M:={a}.

Крок 2. Оновлення міток. Для кожної вершини v є Г(x)\M замінити мітки: l(v):= min{l(v); l(x)+w(x,v)}, тобто оновлювати тимчасові мітки вершин, у які з вершини x іде дуга.

Крок 3. Перетворення мітки в постійну. Серед усіх вершин із тимчасовими мітками знайти вершину з мінімальною міткою, тобто знайти вершину v* з умови l(v*) = min{l(v)}, v є T, де T = V\M.

Крок 4. Уважати мітку вершини v* постійною і виконати M:=MÈ{v*}; x:=v* (вершину v* включено в множину М).

Крок 5. а) Для пошуку шляху від a до z; якщо x = z, то l(z) – довжина найкоротшого шляху від a до z; зупинитись; якщо x!=z, то перейти до кроку 2.

б) Для пошуку шляхів від a до всіх інших вершин: якщо всі вершини отримали постійні мітки (включені в множину М) то ці мітки дорівнюють довжинам найкоротших шляхів, зупинитися; якщо деякі вершини мають тимчасові мітки, то перейти до кроку 2.