Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Дейкстри

Розглянемо деякий орієнтований гряф, для якого потрібно знайти найкоротший маршрут від вершини 1 до всіх інших вершин. Для розв'язку задач такого типу доцільно використовувати алгоритм Дейкстри.

Слідуючи алгоритму, початковій вершині (вершина під номером 1) присвоюємо постійну мітку після чого переходимо до першого етапу.

Етап 1: з вершини 1 існує орієнтоване ребро до вершин 2, 4 і 5. Обчислимо для даних вершин відповідні мітки. В результаті отримаємо наступну таблицю.

Серед вершин з тимчасовими мітками, вибиремо ту, значення відстані для якої є найменшим. В нашому випадку такою є вершина 4, з відстанню . Міняємо статус даної вершини на «постійна» і переходимо до другого етапу.

Етап 2: з четвертої вершини існує орієнтоване ребро до вершин 3 і 5. Обчислюємо для них мітки, після чого таблиця набуде наступного вигляду.

В даній таблиці, тимчасову мітку [100, 1] для вершини 5, отриману на попередньому етапі, замінено на нову [50, 4], також тимчасову мітку. Це говорить про те, що до вершини 5 знайдено більш короткий маршрут, який проходить через вершину 4. Пісял чого, аналогічно першому етапу, вибираємо вершину значення відстані для якої є найменшим (вершина під номером 2) і міняємо  її статус на постійну.

Етап 3: від вершини 2 не можливо потрапити до інших вершин графа, тому на даному етапі ми отримаємо аналогічну другому етапу таблицю, тільки статус вершини 2 змінено на постійна.

Серед вершин, статус мітки яких не дорінює постійна, вибираємо ту, для якої значення відстані є найменшим. Тобто вершину 5, для якої . Міняємо її статус на постійну і переходимо до четвертого етапу.

Етап 4: з вершини 5 не існує орієнтованих ребер до інших вершин графа, тому таблиця міток залишається незмінною, тільки статус вершини 5 замінено на постійну.

На четвертому етапі, ми отримали таблицю, в якій з тимчасовою міткою залишилась тільки вершина 3. І виходячи з того, що з даної вершини можна потрапити у вершину 2 або 5, статус яких становить — постійна, то на цьому процес обчислень за алгоритмом Дейкстри закінчується.

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