Знаходження найкоротшого шляху в орієнтованому графі за алгоритмом Дейкстри
Алгоритм Дейкстри, на відміну від алгоритму Флойда з допомогою якого можна відшукати найкоротший маршрут між будь-якими двома вершинами графа, призначений для пошуку маршруту найкоротшої довжини від заданої вершини графа до всіх інших. В процесі виконання даного алгоритму при переході від вершини i до вершини j використовується спеціальна процедура, яка кожній вершині графа присвоює відповіду мітка.
Позначемо через найкоротша відстань від початкової вершини 1 до вершини i, через
— довжину ребра (i, j). Тоді для вершини j мітка
визначається наступним чином:
Мітки в алгоритмі Дейкстри можуть бути двох типів: тимчасові або постійні. Тимчасова мітка може бути замінена на нову також тимчасову, якщо в процесі виконання алгоритму буде знайдено більш короткий маршрут до даної вершини. Якщо ж в процесі виконання алгоритму виявиться, що більш короткого маршруту від початкової до даної вершини не існує, то змінюємо статус тимчасової мітки на постійну.
Розв'язок за алгоритмом Дейкстри складається з наступних етапів:
- Початковій вершині (вершина під номером 1) присвоюємо постійну мітку
і покладаємо
.
- Для всіх вершин j, які поєднані орієнтованим ребром з вершиною i, і не мають міток, статус яких становить «постійна», обчислюємо тимчасові мітки
. Якщо для вершина j вже існує деяка мітка
, то слід провірити виконання умови
. Виконання даної умови говорить про те, що необхідно мітку
замінити на
.
Даний процес продовжуємо до тих пір, поки всім вершинам графа не буде присвоєно мітку зі статусом — постійна.