Презентация на тему “Алгоритми пошуку оптимального рішення задачі та найкоротшого шляху”

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

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

Хвильовий алгоритм

всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для

графів без циклів від'ємної довжини.

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

заданої вершини до всіх інших. Ідея в тому, що

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

i от 1 до |V| виконати Для j от

1 до |V| виконати Якщо вага i->k и k->j не нульові, и i не рівно j, то Якщо вага i->k + вес k->j меньше веса i->j, то заменить его их суммой

Матриця суміжності

усіма парами вершин зваженого орієнтованого графу. Цей алгоритм працює,

якщо у графі містяться ребра з додатними чи від’ємними вагами, але відсутні негативні цикли.

вершини до іншої або до всіх вершин графу і

ваги всіх ребер графу є додатними або дорівнюють нулю, то найбільш ефективним виявляється алгоритм Дейкстри із часом роботи О(m lgn). Якщо ж ваги ребер можуть бути від’ємними, то необхідно застосовувати алгоритм Белмана-Форда, час роботи якого О(nm).
Якщо необхідно знайти відстані між усіма парами вершин графу, граф є розрядженим і всі ребра мають невід’ємні ваги, то можна виконати n разів алгоритм Дейкстри. Якщо ж граф є розрядженим, але в ньому можуть бути ребра з від’ємними вагами, то необхідно використовувати алгоритм Джонсона. Якщо необхідно знайти відстані між усіма парами вершин, ваги ребер можуть бути від’ємними і граф не є розрядженим (m прямує до n2), то необхідно використовувати алгоритм Флойда-Уоршола.
Жоден з наведених алгоритмів не може бути застосований для графів, які містять негативні цикли. Проте алгоритм Белмана-Форда (як і алгоритм Джонсона), а також алгоритм Флойда-Уоршола можуть виявити такі цикли.