Знаходження найкоротшого шляху в орієнтованому графі за алгоритмом Дейкстри

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

Позначемо через найкоротша відстань від початкової вершини 1 до вершини i, через  — довжину ребра (i, j). Тоді для вершини j мітка визначається наступним чином:

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

Розв'язок за алгоритмом Дейкстри складається з наступних етапів:

1. Початковій вершині (вершина під номером 1) присвоюємо постійну мітку і покладаємо .
2. Для всіх вершин j, які поєднані орієнтованим ребром з вершиною i, і не мають міток, статус яких становить «постійна», обчислюємо тимчасові мітки . Якщо для вершина j вже існує деяка мітка , то слід провірити виконання умови . Виконання даної умови говорить про те, що необхідно мітку  замінити на .

Даний процес продовжуємо до тих пір, поки всім вершинам графа не буде присвоєно мітку зі статусом — постійна.