Лекція 3.1. Розробка й оцінка алгоритмів пошуку найкоротших шляхів у графах

Нехай G=(V,A) – орієнтований зважений граф. Задача про найкоротший шлях складається у відшуканні шляху мінімальної ваги, що з'єднує задані початкову і кінцеву вершини графа G за умови, що хоча б один такий шлях існує. Початкову і кінцеву вершини позначимо відповідно через s і t; (s,t) – шлях мінімальної ваги будемо називати найкоротшим (s,t) – шляхом.

1. Алгоритм пошуку найкоротших шляхів у графах з невід’ємними вагами всіх дуг. Отже, розглядаємо графи, у яких w(e)>=0 для кожної дуги e(A. У цьому випадку розв’язок задачі про найкоротший шлях є істотно менш трудомістким, чим у загальному. Перший ефективний алгоритм побудови найкоротшого шляху в графі з невід’ємними вагами дуг запропонував Е. Дейкстра в 1959 р.

На кожній ітерації цього алгоритму будь-яка вершина v графа G має мітку l(v), що може бути постійною або тимчасовою. У першому випадку l(v) – вага найкоротшого (s,v) – шляху. Якщо ж мітка l(v) тимчасова, то l(v) – вага найкоротшого (s,v) – шляху, що проходить тільки через вершини з постійними мітками. Таким чином, тимчасова мітка l(v) є оцінкою зверху для ваги найкоротшого (s,v) – шляху, і ставши на деякій ітерації постійної, вона залишається такий до кінця роботи алгоритму. Крім l(v), з кожною вершиною v графа G, за винятком s, зв'язується ще одна мітка - ((v). На кожній ітерації ((v) є номер вершини, що передує v у (s,v) – шляхів, що проходять через вершини, що одержали до даного моменту постійні мітки. Після того як вершина t одержала постійну мітку, за допомогою міток ((v) легко вказати послідовність вершин, що складають найкоротший (s,t) – шлях.

Перед початком першої ітерації алгоритму вершина s має постійну мітку l(s) =0, а мітки l всіх інших вершин рівні  і ці мітки тимчасові.

Загальна ітерація алгоритму складається в наступному. Нехай p – вершина, що одержала постійну мітку l(p) на попередній ітерації. Переглядаємо усі вершини v(Г(р), що мають тимчасові мітки, з метою зменшення (якщо це можливо) цих міток. Мітка l(v) вершини v(Г(р) замінюється на l(p)+w(p,v), якщо виявилося, що вершина v одержала свою мітку l з вершини p, і думаємо ((v)=p. Якщо ж l(v)<=l(p)+w(p,v), то мітки ( і l вершини v не змінюються на даній ітерації. Алгоритм закінчує роботу, коли мітка l(t) стає постійною. Як вже говорилося вище, l(t) -найкоротшого (s,t) -шляху, що будемо позначати через P*. Цей шлях визначається за допомогою міток  так:

P*=(s, ..., ³(t), ²(t), (t),t),

Де ^k=((...((v) ...)) для будь-якої вершини v ( VG.

K раз

Будемо вважати, что граф G заданий матрицею ваг або списками суміжності.

Алгоритм A4 Дийкстры пошуки найкоротшого шляху.

Мал. 75.2

1. Покласти l(s):=0 і вважати цю мітку постійною. Покласти l(v) := ( для всіх v ( VG, v(s, і вважати ці мітки тимчасовими. Покласти p:=s.

2. Для всіх v ( Г(p) з тимчасовими мітками виконати: якщо l(v)>l(p)+w(p,v), те l(p):=l(p)+w(p,v) і ((v):=p. Інакше l(v) і ((м) не змінювати.

3. Нехай V' – безліч вершин з тимчасовими мітками l. Знайти вершину v*, таку що

l(v*) = min l(v).

v(V(

Вважати мітку l(v*) постійною міткою вершини l(v*).

4. p := v*. Якщо p = t, то перейти до п. 5 [l(t) – вага найкоротшого шляху]. Інакше прейти до п. 2.

5 .

[P* – найкоротший шлях]. Кінець.

Перш ніж перейти до обґрунтування алгоритму, зробимо три корисних зауваження.

Зауваження 1. Як легко бачити, алгоритм А5 застосовуємо до змішаного і , в частково, до неорієнтованих графам. Для цього досить кажне неориєнтоване ребро uv графу, що має вагу w(u, v), розглядати як пари дуг (u, v) і (v, u) тієї ж ваги.

Зауваження 2. Якщо п. 4 модифікувати таким чином, щоб алгоритм закінчував роботу тілько після одержання усіма вершинами постійних міток, то він буде будувати найкоротші шляхи з s у кожну з інших вершин. Якщо до того ж разом з перетворенням метки вершини v* у постійну (п. 3 алгоритму) заносити дугу ((v*), v*) у безлічі А*, то після закінчення роботи алгоритму граф D = (VG, A*) буде кореневим орієнтованим кістяковим деревом. Це дерево називається деревом найкоротших шляхів з s графа G. Для будь-якої вершини vVG єдиний шлях (s, v)-шлях у дереві D є найкоротчшим (s, v)-шляхом у графі G.

Зауваження 3. Алгоритм А5, модифікований так, як зазначено в зауваженні 2, можна розглядати як алгоритм побудови дерева D найкоротших шляхів з вершин s графа G. З цього погляду алгоритм А5 анологічен алгоритму А3 побудови мінімального кістяка. дійсно, побудова дерева D складається в послідовному збільшенні вже побудованого фрагменту шляхом додавання деякої дуги, “вихідної” з цього фрагмента. При цьому влучні l і  грають таку ж роль, як і мітки  і  в алгоритмі А3.

Т еорема 76.1. Алгоритм А5, будує в графе G найкоротший (s, t)-шлях за час

Доказ. Помітимо спочатку, що мітка вершини v (l(v) (() дорівнює вазі (s, v)-шляху, що побудований алгоритмом до цього моменту. Він визначається мітками (, що маються на цей момент. Тому для доказу оптимальності (s, t)-шляху, що відповідає постійній мітці l(t), досить довести, що постійна мітка l(v) кожної вершини v дорівнює ваги найкоротшого (s, v)-шляху. Це твердження будемо доводити по індукції. Нехай вершина v отримала свою постійну мітку на k-й ітерації, тобто після k-го виконання п. 3. При k = 1 справедливість твердження очевидна. Припустимо, що воно вірно для вершин, що одержали свої постійні мітки на ітераціях 2, 3, ..., k – 1. Позначимо через P( (s, t)-шлях, побудований алгоритмом у результаті k ітерацій, а через Р* – найкоротший (s, v)-шлях. За умовою w(P() = l(v).

Нехай V1 і V2 – безлічі вершин, що мають відповідно постійні і тимчасові мітки перед початком k-ї ітерації. Розглянемо дві можливі ситуації:

а) Шлях Р* містить вершини з V2. Нехай (v – перша (вважаючи від s) така вершина, що належить Р*, а вершина v( передує(v на шляху Р*, тобто (v(,(v)(AP*. Відповідно до вибору(v маємо v((V1. Позначимо через Р1* частину шляху Р* від s до(v. По припущенню індукції l((v) – вага найкоротшого (s, (v)-шляху. Тому

w(Р1* ) = l((v) + w(v((v) ( l((v).

Оскільки l((v) – тимчасова мітка, а остання мітка l(v) вершини v вибирається на k-й ітерації як найменша з тимчасових, то l((v) ( l(v). Об'єднавши цю нерівність з (1), одержимо

w(P*) ( w(P1*) ( l(v) = w(P(),

т. ч. P( – найкоротший (s, t)-шлях.

б) Усі вершини шляху Р* входять у V1. Нехай v( і v(( – такі вершини, що (v(, v)(АР* і (v((, v)(АР(. Позначимо через Р( частина шляху Р* від s до v(, відповідно до припущення індукції маємо w(P() ( l(v(). Тому, якщо v( = v((, то відразу одержуємо нерівність

w(P*) = w(P() + w(v(, v) ( l(v() + w(v(, v) = w(P().