Алгоритм Дейкстри і його реалізація
У математичній науці і інформатики існуєокремий напрямок, зване теорією графів. В рамках її ставляться і вирішуються різноманітні завдання, наприклад, про знаходження найкоротшого шляху між вершинами. Одним з поширених серед математиків способів вирішення цього завдання давно вже став алгоритм Дейкстри.
Вважається, що поняття графа було введено впобут у вісімнадцятому столітті Леонардом Ейлером. Саме він озвучив постановку і вирішення однієї з класичних задач цієї теорії - про сім мостах Кенігсберга. Для того щоб пояснити об'єкт цієї теорії, найчастіше користуються такою аналогією, як пересування між різними містами. Тоді граф на площині буде являти собою всю схему маршрутів, де вершинами стануть конкретні пункти (наприклад, міста), а ребрами - шляхи з однієї вершини в іншу (аналог дороги між містами). Алгоритм Дейкстри, крім інших способів, може дати рішення цього питання.
Однією зі стандартних завдань теорії графів єта, в якій потрібно визначити оптимальний за витратами шлях між двома точками. Її можна звести на площині до вирішення графа, в якому вершини - міста - пов'язані між собою ребрами, що представляють собою можливі дороги. Причому кожна дорога має свою довжину, отже, на проїзд по ній доведеться витратити певні кошти. Ця сума еквівалентна вазі ребра на графі. Тоді завдання на практиці можна сформулювати так: як прокласти шлях з одного міста в інший, щоб витратити на дорогу мінімальні кошти.
способи вирішення
Для вирішення цього завдання були придумані деякіалгоритми, які стали широко відомі в науковому світі. Наприклад, алгоритм Флойда - Уоршелла, Форда - Беллмана. Класичним способом знаходження рішення є також алгоритм Дейкстри. Він може використовуватися і для зваженого (відомий вага кожного ребра) графа, і для розрідженого. Для знаходження остаточного шляху потрібно виконати кілька кроків.
алгоритм Дейкстри
Сенс цього способу полягає в тому, щообходяться все вершини, починаючи з заданої, при цьому кожній присвоюється мітка з деяким значенням. Потім в результат увійдуть ті вершини, мітки яких мінімальні. На першому кроці вихідної вершині присвоюється мітка зі значенням 0. Потім розглядаються всі наступні вершини, тобто ті, в які можна потрапити з вихідної. Їм присвоюються мітки, значення яких визначається як сума исходника і ваги шляху. З вершин наступного кроку вибирається та, що має найменше значення мітки, і вивчаються всі вершини, в які з неї можна пройти, не використовуючи проміжних вершин. Визначається нове значення мітки, рівне мітці вершини - исходника плюс вага шляху. Якщо отримане значення менше, ніж мітка вершини, то мітка змінюється. В іншому випадку залишається початкове значення. При цьому в окремому масиві, розмірність якого дорівнює кількості вершин графа, зберігається результат оптимізації, за яким і визначається шлях. Для реалізації такого способу, як алгоритм Дейкстри, Pascal пропонує дуже зручні засоби. Алгоритм має ту перевагу, що легко може бути покладено в основу програми, яка має невеликий розмір. Приклади таких програмних продуктів легко знайти в мережі Інтернет.
