Алгоритм пошуку найкоротшого шляху

Результатом алгоритму пошуку найкоротшого шляху є послідовність ребер, що з'єднує задані дві вершини і має найменшу довжину серед всіх таких послідовностей.
На перший погляд здається, що ми можемо скористатися алгоритмом побудови МОД, щоб відкинути зайві ребра, а потім взяти шлях, що з'єднує задані вершини в побудованому остовном дереві. На жаль, такі дії не завжди приводять до потрібного результату.
Нагадаємо, що алгоритм побудови МОД націлений на пошук дерева з мінімальним сумарним вагою ребер. Розглянемо, наприклад, "циклічний" граф, тобто такий граф, в якому перша вершина з'єднана з другою, друга - з третьої, і так далі, а остання вершина в свою чергу сполучена з першою. Такий граф являє собою просто кільце, кожна вершина в якому з'єднана з двома іншими. Приклад такого графа з шістьма вершинами наведено на рис. 1 (а).

Зверніть увагу на те, що вага кожного ребра дорівнює 1 за винятком ребра, що з'єднує вершини A і B, вага якого дорівнює 2. Алгоритм побудови мінімального остовного дерева вибере все ребра ваги 1, відкинувши єдине ребро ваги 2. Це означає, однак, що шлях від A до B в мінімальному остовном дереві повинен проходити через всі інші вершини, а його довжина дорівнює 5 (рис. 1 (б)). Ясно, що він не є найкоротшим, оскільки в вихідному графі вершини A і B з'єднані ребром довжини 2.

алгоритм Дейкстри
Жадібний алгоритм побудови мінімального остовного дерева непридатний для пошуку найкоротшого шляху між двома вершинами, оскільки на кожному проході він враховує довжину лише одного ребра. Якщо ж змінити його так, щоб при виборі ребра, провідного в облямівку, він вибирав ребро, що є частиною найкоротшого шляху в цілому шляху з початкової вершини, то ми отримаємо необхідний результат. Точніше кажучи, ось змінений алгоритм: На рис. 2 наведено приклад виконання цього алгоритму. Алгоритм виконується на тому ж графі (рис. 2 (а)), що і алгоритм побудови мінімального остовного дерева, а шукати ми будемо найкоротший шлях від A до G.

На початку шляху з вершини A у нас є чотири можливих ребра. З цих чотирьох ребер ребро AB є найкоротшим. Тому ми додаємо до дерева вершину B (рис. 2 (в)) і дивимося, як слід оновити набір шляхів. З уже побудованим деревом з'єднані тепер вершини E і G, тому їх слід додати до каймі. Крім того, ми повинні подивитися на вершину D і порівняти прямий шлях з неї в A, довжина якого дорівнює 7, з обхідним шляхом через вершину B, довжина якого дорівнює 8. Прямий шлях коротше, тому приписане до D ребро міняти не слід. Вивчивши тепер наявні можливості, ми бачимо, що найкоротшим є шлях з A в C довжини 4. Ребро BE коротше, однак, ми розглядаємо повну довжину шляху з A, а такий шлях, що веде в E, має довжину 5. Тепер до дерева найкоротших шляхів додамо вершину C (рис. 2 (г)). Подивившись на граф, ми виявляємо, що можемо пройти в вершину F через вершину C, проте довжина цього шляху буде дорівнює 10 - більше, ніж у прямого шляху з A в F, тому зміни в наборі шляхів не проводиться.
На рис. 2 (г) ми можемо вибрати тепер або шлях з A в F, або шлях з A в E, що проходить через вершину B: обидва вони мають довжину 5. Який із шляхів буде обраний при виконанні програми, залежить від способу зберігання даних в ній. Ми ж, зустрівшись з необхідністю додати вершину, будемо завжди вибирати вершину, мітка якої перша в лексикографічному порядку.

В результаті отримаємо ситуацію з рис. 2 (д). Додавання до дерева вершини E не змінює інших зв'язків, тому тепер ми можемо додати вершину F і отримаємо картинку з рис. 2 (е). Зверніть увагу на те, що, хоча додавання вершини F і призвело до зміни ребра, що веде з D, якби ми почали з F, все одно на черговому кроці ми повинні були б додати E.
На рис. 2 (е) видно, що шлях в вершину D коротше шляху в вершину G. Тому ми додаємо до дерева вершину D і отримуємо ситуацію, зображену на рис. 2 (ж). Залишилося додати тільки вершину G, і в результаті ми отримуємо дерево найкоротшого шляху з рис. 2 (з). Довжина найкоротшого шляху з A в G дорівнює 10.

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