Методы поиска кратчайших путей на графах в организационно-экономических системах и их реализация

Abstract

В статье реализованы функции, в СУБД Postgre SQL, нахождения кратчайших путей на графах, методом волнового алгоритма, методом Дейсктры и методом Флойда. Экспериментально определены модели зависимостей времени работы реализаций алгоритмов поиска кратчайших путей на графах от количества вершин графа. Проведено сравнение полученных в результате исследования данных, для нахождения наилучших применений реализаций алгоритмов поиска кратчайших путей в СУБД Postgre SQL. The article implements the functions for PostgreSQL DBMS, finding the shortest paths in graphs, using the wave algorithm method, the Dijkstra’s method and the Floyd method. The authors determined experimentally the models that show the dependency of the running time of the graph-based shortest-path search algorithms implementation on the number of graph nodes. The authors carried out the comparison of the data obtained as a result of the study to find the best applications of the shortest-path search algorithms implementation in the PostgreSQL DBMS.