НОУ ІНТУЇТ | лекція | найкоротші шляхи

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

В "Мінімальні остовне дерева" було розглянуто алгоритм Прима для знаходження мінімального остовного дерева (MST) зваженого неориентированного графа: ми будуємо його, додаючи на кожному кроці найкоротший ребро, яке з'єднує вершину з MST з вершиною, ще не входить до MST. Для обчислення SPT можна скористатися майже такий же схемою. Спочатку ми заносимо в SPT витік, а потім будуємо SPT, додаючи на кожному кроці одне ребро, яке формує найкоротший шлях з витоку в вершину, що не включена до SPT. Тобто вершини заносяться в SPT в порядку їх відстані (по SPT-дереву) від початкової вершини. Цей метод називається алгоритмом Дейкстри (Dijkstra).

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

Лемма 21.2. Алгоритм Дейкстри вирішує завдання пошуку найкоротших шляхів з одного джерела в мережах з невід'ємними вагами.

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

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

Доказ не спрацьовує, якщо ваги ребер можуть бути негативними, оскільки в ньому передбачається, що при додаванні ребер до шляху довжина шляху не зменшується. У мережі з негативними вагами ребер це припущення є недійсною, оскільки будь-яке зустрінуте ребро, що веде в деяку вершину дерева і має досить великий негативний вагу, може дати більш короткий шлях в цю вершину, ніж шлях в дереві. Цей момент буде розглянуто в розділі 21.7 (див. Мал. 21.28 ).

на Мал. 21.10 показано розгортання SPT при обчисленні за алгоритмом Дейкстри, а на Мал. 21.11 показаний малюнок більшого орієнтованого SPT-дерева. Хоча алгоритм Дейкстри відрізняється від алгоритму Прима для обчислення MST тільки вибором пріоритету, SPT-дерева мають характерні особливості, що відрізняють їх від MST. Їх корінь розташований в початковій вершині, а все ребра спрямовані в бік від кореня, тоді як в MST немає ні кореня, ні напрямків. При використанні алгоритму Прима ми іноді уявляємо MST-дерева як спрямовані дерева з корінням, але такі структури все одно істотно відрізняються від SPT (порівняйте орієнтоване зображення на Мал. 20.9 із зображенням на Мал. 21.11 ). Взагалі-то природа SPT частково залежить і від вибору початкової вершини (див. Мал. 21.12 ).

Первісна реалізація Дейкстри, яка годиться для насичених графів, в точності відповідає алгоритму Прима для обчислення MST. Ми просто замінюємо присвоювання пріоритету P в програмі 20.6

P = e-> wt () (вага ребра) на P = wt [v] + e-> wt ()

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

Лемма 21.3. За допомогою алгоритму Дейкстри можна знайти будь-SPT в насиченою мережі за лінійний час.

Доведення. Як і в разі алгоритму Прима для обчислення MST, після перегляду коду програми 20.6 очевидно, що час виконання пропорційно V2, тобто лінійно для насичених графів.

У разі розріджених графів можливо удосконалення. Алгоритм Дейкстри можна розглядати як узагальнений метод пошуку на графі, який відрізняється від пошуку в глибину (DFS), від пошуку в ширину (BFS) і від алгоритму Прима для обчислення MST тільки правилом додавання ребер в дерево. як і в "Мінімальні остовне дерева" , Ребра, які з'єднують вершини дерева з вершинами, які не включені в дерево, містяться в узагальненій черзі, званої накопичувачем (fringe). Для реалізації цієї узагальненої черзі використовується чергу з пріоритетами і механізм зміни пріоритетів, що дозволяє об'єднати в одній реалізації алгоритми DFS, BFS і Прима (див. "Мінімальні остовне дерева" ). Ця схема пошуку по пріоритетам (PFS) включає і алгоритм Дейкстри. Тобто заміна оператора присвоювання P в програмі 20.7 на

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

Мал.21.10.

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

Ця послідовність показує побудова алгоритмом Дейкстри остовного дерева найкоротших шляхів для мережі з коренем у вершині 0. Жирними чорними лініями на діаграмах мереж показані ребра дерева, а жирними сірими - ребра в накопичувачі. Орієнтовані зображення дерева в процесі його росту показані в центрі, а праворуч наведені списки ребер в накопичувачі. Спочатку в дерево заноситься вершина 0, а в накопичувач - виходять з нього ребра 0-1 і 0-5 (малюнок вгорі). На другому кроці ми переносимо найкоротше з цих ребер, 0-5, з накопичувача в дерево і перевіряємо ребра, що виходять з нього: ребро 5-4 заноситься в накопичувач, а ребро 5-1 відкидається, оскільки воно не є частиною більш короткого шляху з 0 в 1, ніж відомий шлях 0-1 (другий малюнок зверху). Пріоритет ребра 5-4 в накопичувачі дорівнює довжині поданого ним шляху 0-5-4 з вершини 0. На третьому кроці ми переносимо ребро 0-1 з накопичувача в дерево, заносимо в на-копітель ребро 1-2 і відкидаємо 1-4 ( третій зверху малюнок). На четвертому кроці ми переносимо 5-4 з накопичувача в дерево, заносимо в накопичувач 4-3 і замінюємо 1-2 на 4-2, тому що шлях 0-5-4-2 коротше, ніж 0-1-2 (четвертий зверху). Ми тримаємо в накопичувачі не більше одного ребра, що веде до кожної вершині, і вибираємо з них те, що лежить на найкоротшому шляху від 0. Обчислення завершується переносом з накопичувача в дерево ребра 4-2, а потім 4-3 (малюнок внизу).

Мал.21.11.

Кістяк найкоротших шляхів

Тут показана робота алгоритму Дейкстри для вирішення завдання пошуку найкоротших шляхів з одного джерела в випадковому Евклідовому орграфе з сусідніми зв'язками (з двонаправленими ребрами, відповідними кожної накресленої лінії) - в тому ж стилі, що і Мал. 18.13 , Мал. 18.24 і Мал. 20.9 Дерево пошуку схоже на BFS, тому що вершини зазвичай з'єднуються один до іншому короткими шляхами, але воно злегка більш витягнуте і менш широке, оскільки використання відстаней призводить до трохи більш довгим шляхам, ніж використання довжин шляхів.

Мал.21.12.

Приклади SPT-дерев

Ці три приклади демонструють зростання SPT для трьох різних положень витоку: ліве ребро (вгорі), верхній лівий кут (в центрі), і центр (внизу).

Програма 21.1. Алгоритм Дейкстри (пошук по пріоритетам)

Цей клас реалізує АТД для пошуку найкоротших шляхів з одного джерела з лінійним часом попередньої обробки, приватними даними, які займають обсяг пам'яті, пропорційний V, і функціями-членами з постояннно часом виконання, які повертають довжину найкоротшого шляху і кінцеву вершину шляху з витоку в будь-яку задану вершину. Конструктор реалізує алгоритм Дейкстри, використовуючи для обчислення SPT чергу з пріоритетами вершин (в порядку їх видалення від витоку). Інтерфейс черзі з пріоритетами - той же, який використовується в програмі 20.7 і реалізований в програмі 20.10.

Конструктор виконує узагальнений пошук на графі, який реалізує інші алгоритми PFS з іншими призначеннями пріоритету P (див. Текст). Оператор обнулення ваги вершин дерева необхідний для загальної реалізації PFS, але не для алгоритму Дейкстри, тому що пріоритети вершин, що додаються в SPT, є неубутних.

template <class Graph, class Edge> class SPT {const Graph & G; vector <double> wt; vector <Edge *> spt; public: SPT (const Graph & G, int s): G (G), spt (GV ()), wt (GV (), GV ()) {PQi <double> pQ (GV (), wt); for (int v = 0; v <GV (); v ++) pQ.insert (v); wt [s] = 0,0; pQ.lower (s); while (! pQ.empty ()) {int v = pQ.getmin (); // wt [v] = 0,0; if (v! = s && spt [v] == 0) return; typename Graph :: adjIterator A (G, v); for (Edge * e = A.beg ();! A.end (); e = А.пх ^)) {int w = e-> w (); double P = wt [v] + e-> wt (); if (P <wt [w]) {wt [w] = P; pQ.lower (w); spt [w] = e; }}}} Edge * pathR (int v) const {return spt [v]; } Double dist (int v) const {return wt [v]; }};

Програма 21.1 є альтернативною реалізацією PFS для розріджених графів; вона дещо простіше програми 20.7 і безпосередньо відповідає неформальному опису алгоритму Дейкстри на початку цього розділу. Вона відрізняється від програми 20.7 тим, що спочатку всі вершини мережі заносяться в чергу з пріоритетами, і ті вершини в цій черзі, які не перебувають ні в дереві, ні в накопичувачі, позначаються сигнальними значеннями (невидимі вершини з сигнальними значеннями). А програма 20.7 містить в черзі з пріоритетами тільки вершини, досяжні з дерева через одне ребро. Зберігання всіх вершин в черзі спрощує код, хоча для деяких графів може злегка погіршити ефективність (див. Вправу 21.31).

Загальні значення продуктивності пошуку по пріоритетам (PFS), розглянуті в "Мінімальні остовне дерева" , Дають нам конкретну інформацію про ефективність цих реалізацій алгоритму Дейкстри для розріджених графів (програма 21.1 і програма 20.7, з відповідними змінами). Для зручності ми приведемо їх ще раз, але вже в поточному контексті. Оскільки докази не залежать від функції обчислення пріоритету, їх можна застосувати без змін. Це результати для найгіршого випадку і обох програм, хоча програма 20.7 може виявитися більш ефективною для багатьох класів графів, оскільки вона використовує менший накопичувач.

Лемма 21.4. Для всіх мереж і всіх функцій пріоритетів можна обчислити кістяк за допомогою PFS за час, пропорційне часу, необхідного для виконання V операцій вставити, V операцій видалити мінімальне і E операцій зменшити ключ в черзі з пріоритетами розміром не більше V.

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

Лемма 21.5. За допомогою реалізації алгоритму Дейкстри на основі PFS, що використовує пірамідальне дерево для реалізації черги з пріоритетами, можна обчислити будь-SPT за час, пропорційне E lgV.

Доведення. Цей результат є прямим наслідком леми 21.4. | Лемма 21.6. Нехай заданий граф з V вершинами, E ребрами і насиченістю d = E / V. Якщо d <2, то час виконання алгоритму Дейкстри пропорційно VlgV Інакше реалізація черги з пріоритетами на основі -арної пірамідального дерева дозволяє поліпшити час виконання в гіршому випадку не менше ніж в lg (E / V) раз - до (Що лінійно, якщо E одно принаймні ).

Доведення. Цей результат безпосередньо випливає з леми 20.12 і реалізації черги з пріоритетами на основі багатоколійні пірамідальних дерев, яка розглянута після цієї леми.

У таблиці 21.1 зведена інформація про розглянутих нами чотирьох основних алгоритмах PFS. Вони відрізняються лише використовуваної обчисленням пріоритету, але ця різниця призводить до абсолютно різних остовне деревам (як і повинно бути). Наприклад, на малюнках, що згадуються в таблиці (і для багатьох інших графів), дерево DFS є високим і вузьким, дерево BFS - низьким і широким; SPT схоже на дерево BFS, але не таке низьке і широке, а MST - не низька і широке, але і не високе й вузьке.

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

Таблиця 21.1. Алгоритми пошуку за пріоритетами Алгоритм Пріоритет Результат Малюнок DFS Звернення прямого обходу Дерево рекурсії 18.13 BFS Прямий обхід SPT (ребра) 18.24 Прима Вага ребра MST 20.8 Дейкстри Вага шляху SPT 21.9

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

• Ребра з накопичувача (програма 18.10)
• Вершини з накопичувача (програма 20.7)
• Всі вершини (програма 21.1).

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

У цій таблиці наведено витрати (час виконання в гіршому випадку) різних реалізацій алгоритму Дейкстри. При відповідних реалізаціях черг з пріоритетами алгоритм виконується за лінійний час (пропорційне V2 для насичених мереж і пропорційне E для розріджених мереж), за винятком дуже розріджених мереж.

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

Назва алгоритм Дейкстри зазвичай використовується для позначення як абстрактного методу побудови SPT покроковим додаванням вершин в порядку їх відстані від витоку, так і його реалізації у вигляді алгоритму з часом виконання, пропорційним V2, для подання матрицею суміжності, оскільки Дейкстра представив і те, і інше в своїй статті, опублікованій в 1959 р (а також показав, що цим методом можна обчислити і MST). Підвищення продуктивності на розріджених графах пов'язано з наступними удосконаленнями в технології АТД і реалізації черги з пріоритетами, які не призначені для задач пошуку найкоротших шляхів. Більш висока продуктивність алгоритму Дейкстри - одне з найбільш важливих властивостей цієї технології (див. Розділ посилань). Як і у випадку з MST, для вказівки конкретних сполучень ми застосовуємо такі терміни, як "реалізація алгоритму Дейкстри на основі PFS з використанням пірамідальних d-дерев".

В "Пошук на графі" було показано, що при використанні в невиважених неорієнтованих графах прямої нумерації для пріоритетів чергу з пріоритетами діє як чергу FIFO і призводить до пошуку в ширину (BFS). Алгоритм Дейкстри дає іншу реалізацію BFS: коли все ваги ребер рівні 1, він відвідує вершини в порядку нумерації ребер на найкоротшому шляху до початкової вершини. В цьому випадку чергу з пріоритетами діє не зовсім так, як чергу FIFO, тому що елементи з однаковими пріоритетами необов'язково витягуються з черги в тому порядку, в якому вони були занесені в неї.

Кожна з цих реалізацій поміщає ребра SPT-дерева з вершини 0 в індексований іменами вершин вектор spt, а в індексований іменами вершин вектор wt - довжини найкоротших шляхів в кожну вершину SPT, і містить функції-члени, що забезпечують клієнтам доступ до цих даних. Як завжди, на основі цих первинних даних можна побудувати різні функції і класи обробки графів (див. Вправи 21.21-21.28).

вправи

21.19. Покажіть в стилі Мал. 21.10 результат обчислення алгоритмом Дейкстри SPT для мережі, яка визначається у вправі 21.1, з початковою вершиною 0.

21.20. Як знайти другий найкоротший шлях в мережі з s в t?

21.21. Напишіть клієнтську функцію, яка використовує об'єкт SPT для пошуку вершини, найбільш віддаленої від заданої вершини s (вершина, найкоротший шлях до якої з s є найбільш довгим).

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

21.23. Розробіть на основі програми 21.1 клас з функцією-членом path, яка повертає значення типу vector з бібліотеки STL, що містить покажчики на ребра найкоротшого шляху, що з'єднує s і t в напрямку від s до t.

21.24. Напишіть клієнтську функцію, яка використовує клас з вправи 21.23 для виведення найкоротших шляхів із заданої вершини в інші вершини заданої мережі.

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

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

21.27. Реалізуйте клас, який використовує об'єкти SPT для аналізу чутливості ребер мережі по відношенню до заданої парі вершин s і t. Обчисліть таку матрицю розміром V х V, що для кожного u і v елемент на перетині рядка u і шпальти v дорівнює 1, якщо в мережі існує ребро uv, збільшення ваги якого не призводить до збільшення довжини найкоротшого шляху з s в t, і дорівнює 0 в іншому випадку.

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

21.29. Скористайтеся рішенням з вправи 21.28 для реалізації клієнтської функції, яка знаходить найкоротший шлях від лівого ребра до правого ребра в випадкової гратчастої мережі (див. Вправу 20.17).

21.30. Покажіть, що MST неориентированного графа еквівалентно SPT-дереву критичних ребер (bottleneck SPT) цього графа: для кожної пари вершин v і w воно дає з'єднує їх шлях, найбільш довге ребро якого має мінімально можливу довжину.

21.31. Емпірично порівняйте продуктивність двох версій алгоритму Дейкстри для розріджених графів, які описані в цьому розділі (програма 21.1 і програма 20.7, з відповідним визначенням пріоритету), для різних мереж (див. Вправи 21.4-21.8). Скористайтеся реалізацією черзі з пріоритетами на основі стандартного пірамідального дерева.

21.32. Емпірично знайдіть оптимальне значення d для реалізації черги з пріоритетами у вигляді пірамідального d-дерева (див. Програму 20.10) для кожної з трьох розглянутих реалізацій алгоритму PFS (програми 18.10, 20.7 і 21.1) і для різних мереж (див. Вправи 21.4-21.8) .

21.33. Емпірично визначте ефект використання реалізації черги з пріоритетами на основі турніру індексного пірамідального дерева (див. Вправу 9.53) в програмі 21.1 для різних мереж (див. Вправи 21.4-21.8).

21.34. Емпірично проаналізуйте висоту і середню довжину шляху в SPT для різних мереж (див. Вправи 21.4-21.8).

21.35. Розробіть клас для завдання пошуку найкоротших шляхів з витоку в стік, заснований на коді на зразок програми 21.1, але в якому спочатку в чергу з пріоритетами заноситься і витік, і стік. При цьому SPT-дерева ростуть з обох вершин; ваше основне завдання - вирішити, що робити при їх зустрічі.

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

21.37. Розробіть прийнятний генератор випадкових графів з V вершинами і E ребрами, для яких час роботи PFS-продажу алгоритму Дейкстри з використанням пірамідального дерева суперлінейно.

21.38. Напишіть клієнтську програму для виконання динамічної графічної анімації роботи алгоритму Дейкстри. Програма повинна створювати зображення на зразок Мал. 21.11 (Див. Вправи 17.56-17.60). Протестуйте програму на випадкових евклідових мережах (див. Вправу 21.9).