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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар