Алгоритм дейкстри і його реалізація

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

Що таке математичний граф

Вважається, що поняття графа було введено в ужиток в вісімнадцятому столітті Леонардом Ейлером. Саме він озвучив постановку і рішення однієї з класичних задач цієї теорії - про сім мостах Кенігсберга. Для того щоб пояснити об`єкт цієї теорії, найчастіше користуються такою аналогією, як пересування між різними містами. Тоді граф на площині буде являти собою всю схему маршрутів, де вершинами стануть конкретні пункти (наприклад, міста), а ребрами - шляхи з однієї вершини в іншу (аналог дороги між містами). Алгоритм Дейкстри, крім інших способів, може дати рішення цього питання.

Відео: Пошук шляху за алгоритмом Дейкстра

Знаходження найкоротшого шляху

Однією зі стандартних завдань теорії графів є та, в якій потрібно визначити оптимальний за витратами шлях між двома точками. Її можна звести на площині до вирішення графа, в якому вершини - міста - пов`язані між собою ребрами, що представляють собою можливі дороги. Причому кожна дорога має свою довжину, отже, на проїзд по ній доведеться витратити певні кошти. Ця сума еквівалентна вазі ребра на графі. Тоді завдання на практиці можна сформулювати так: як прокласти шлях з одного міста в інший, щоб витратити на дорогу мінімальні кошти.

Відео: Лекція 5: Пошук в графах і обхід. алгоритм Дейкстри

способи вирішення

Для вирішення цього завдання були придумані деякі алгоритми, які стали широко відомі в науковому світі. Наприклад, алгоритм Флойда - Уоршелла, Форда - Беллмана. Класичним способом знаходження рішення є також алгоритм Дейкстри. Він може використовуватися і для зваженого (відомий вага кожного ребра) графа, і для розрідженого. Для знаходження остаточного шляху потрібно виконати кілька кроків.

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

Сенс цього способу полягає в тому, що обходяться все вершини, починаючи з заданої, при цьому кожній присвоюється мітка з деяким значенням. Потім в результат увійдуть ті вершини, мітки яких мінімальні. На першому кроці вихідної вершині присвоюється мітка зі значенням 0. Потім розглядаються всі наступні вершини, тобто ті, в які можна потрапити з вихідної. Їм присвоюються мітки, значення яких визначається як сума исходника і ваги шляху. З вершин наступного кроку вибирається та, що має найменше значення мітки, і вивчаються всі вершини, в які з неї можна пройти, не використовуючи проміжних вершин. Визначається нове значення мітки, рівне мітці вершини - исходника плюс вага шляху. Якщо отримане значення менше, ніж мітка вершини, то мітка змінюється. В іншому випадку залишається початкове значення. При цьому в окремому масиві, розмірність якого дорівнює кількості вершин графа, зберігається результат оптимізації, за яким і визначається шлях. Для реалізації такого способу, як алгоритм Дейкстри, Pascal пропонує дуже зручні засоби. Алгоритм має ту перевагу, що легко може бути покладено в основу програми, яка має невеликий розмір. Приклади таких програмних продуктів легко знайти в мережі Інтернет.

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