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

  1. Для заданої початкової вершини знайти найкоротші шляхи від до всіх інших вершин графа.
  2. Знайти найкоротші шляхи між усіма парами вершин.

Виявляється що майже всі методи розв’язання задачі про найкоротший шлях від початкової вершини до заданої вершини також дають змогу знайти й найкоротші шляхи від вершини до всіх інших вершин графа. Отже, за їх допомогою можна розв’язати задачу номер один із невеликими додатковими обчислювальними витратами. З іншого боку, задачу номур два можна розв’язати або  разів застосувавши алгоритм задачі один із різними початковими вершинами, або один раз застосувавши спеціальний алгоритм.

Найефективніший алгоритм визначення довжини найкоротшого шляху від фіксованої вершини до будь-якої іншої запропонував 1959 році датський математик Е. Дейкстра. Цей алгоритм, на відміну від алгоритму Беллмана-Форда, застосований лише тоді, коли вага кожного ребра додатна. Опишемо докладно цей алгоритм для орієнтованого графа.

Отже, нехай  – зважений орієнтований граф, для якого потрібно знайти найкоротші шляхи від виділеної вершини  до всіх інших вершин даного графа.

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

Ілюстрація роботи алгоритму Дейкстри

Перед початком виконання алгорітму всі вершини графа вважаються непройденими, а ребра – не переглянутими. Кожній вершині в ході виконання алгоритму присвоюється число , рівне довжині найкоротшого шляху з вершини  у вершину , що включає тільки пройдені вершини. На першому кроці покладаємо  і  для сіх , відмінних від . Також, на даному кроці, вершині  присвоюється мітка «пройдена» і покладається  ( – остання з пройдених вершин).

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

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

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

Алгоритм Дейкстри – приклад:

Використовуючи алгоритм Дейкстри, знайти найкоротші шляхи від вершини номер один до всіх інших вершин зображеного нижче графа.

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

Орієнтований граф що не містить ребра від’ємної довжини

Отже, згідно з розглянутим алгоритмом, на першому кроці, мітку «пройдена» присвоїмо вершині номер один і в якості величин  для кожної з вершин графа приймаємо наступні значення: .

Далі, поклавши  ( – остання серед пройдених вершин) та скориставшись формулою (1), здійснюємо перерахунок значень , для усіх вершин суміжних з вершиною :

Оскільки значення довжини  є найменшим, то мітку «пройдена» присвоюємо вершині «2». Разом з нею, переглянутим вважається також і ребро , з якого і складається поточне дерево найкоротших шляхів.

Виходячи з того, що переглягуті не всі вершини заданого графа, переходимо до етапу номер два, а саме покладаємо  і, знову-таки, виконуємо перерахунок величин :

Переглянувши отримані результати бачимо, що довжина , на даному етапі, приймає найменшого значення, тому, вершині «5» присвоюємо мітку «пройдена» , а ребро  вважаємо переглянутим. Далі, покладаємо  і виконуємо перерахунок величин :

Після цього, вершина «4» і ребро  вважаються пройденою та переглянутими відповідно і, виходячи з того, що серед вершин заданого графа не всі являються пройденими, покладаємо  та продовжуємо ітераційний процес далі:

З отриманих результатів бачимо, що на даному етапі мітку «пройдена» необхідно присвоїти вершині номер «3» а ребро  позначимо як переглянуте.

Оскільки мітку «пройдена» присвоїно всім вершинам графа, то обчислювальний процес алгоритму Дейкстри завершується.

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

Дерево найкоротших шляхів

Найкоротші шляхи від вершини номер один до всіх інших вершин заданого графа складаються з наступних ребер  (ребра, які, після виконання алгоритму Дейкстри, були помічені як переглянуті).

Блок-схема алгоритму Дейкстри

Алгоритм Дейкстри блок-схема

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

*