Дослідження алгоритмів знаходження оптимальних маршрутів у складі WEB-додатку на базі мікросервісної архітектури

Abstract

Питання прокладання оптимальних маршрутів є актуальним з давніх часів. Серед рішень популярність набули такі алгоритми як Дейкстри, який використовують для прорахунку маршрутів між невід’ємними графами ітераційно, забезпечуючи найліпший результат для кожної вершини, алгоритм А*, особливістю якого є евристичність – використання допоміжної функції задля спрямування і пришвидшення пошуку і не тільки. Головними недоліками алгоритму Дейкстри є неможливість обробки графів, вага яких є від’ємною, та обчислення кожної вершини графу, що здатне знизити продуктивність алгоритму та підвищити використання пам’яті для прорахунку необов’язкових маршрутів.