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

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

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

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

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

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

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

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

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

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