О вариантах практического применения алгоритма Флойда-Уоршалла и его модификаций

Резюме: В статье рассматриваются варианты алгоритма Флойда–Уоршелла, т. е. алгоритмы поиска кратчайших путей во взвешенном графе с заданными весами рёбер; за одно выполнение алгоритма находятся длины кратчайших путей между всеми парами вершин. Хотя стандартные версии алгоритма не возвращают сами найденные пути, эти пути можно реконструировать с помощью простых модификаций алгоритма. Варианты этого алгоритма также могут быть использованы для поиска транзитивного замыкания некоторого бинарного отношения, а также наиболее широких путей между всеми парами вершин взвешенного графа. При этом, по мнению авторов, исследование темы далеко не завершено – что подтверждается, в частности, многими публикациями в Интернете на «алгоритмических» сайтах. Несмотря на то, что кубическая сложность алгоритма решения этой задачи неулучшаема (по крайней мере, для стандартных вариантов представления входных данных), можно стремиться улучшить конкретное время работы алгоритмов. Более того, мы сознательно ухудшаем сложность рассматриваемых нами реализаций алгоритма (фактически умножая её на логарифм числа вершин) – однако за счёт возможности удачного перебора рёбер, ведущегося в порядке увеличения их стоимости, мы добиваемся уменьшения среднего времени работы реализованных программ.

Ключевые слова: графы, алгоритм Флойда–Уоршелла, эвристические алгоритмы, anytime-алгоритмы, AVL-дерево.

B.F. Melnikov, Yu.Yu. Terentyeva

On the practical  applica tion of the Floyd-Warshall algorithm and its modifications

Summary: The paper considers variants of the Floyd – Warshall algorithm, i.e. algorithms for finding shortest paths in a weighted graph with given edge weights; in one execution of the algorithm, the lengths of shortest paths between all pairs of vertices are found. Although the standard versions of the algorithm do not return the paths found, these paths can be reconstructed using simple modifications of the algorithm. Variants of this algorithm can also be used to find the transitive closure of some binary relation, as well as the widest paths between all pairs of vertices of a weighted graph. At the same time, according to the authors, the study of the topic is far from complete; it is confirmed, in particular, by many publications on the Internet on “algorithmic” sites. Despite the fact that the cubic complexity of the algorithm for solving this problem is not improved (at least for standard input data representation options), one can strive to improve the specific running time of the algorithms. Moreover, we deliberately worsen the complexity of the algorithm implementations we are considering (actually multiplying it by the logarithm of the number of vertices); however, due to the possibility of a successful iteration of the edges, conducted in order of increasing their cost, we achieve a reduction in the average running time of the implemented programs.

Keywords: graphs, Floyd–Warshall algorithm, heuristic algorithms, anytime algorithms, AVL tree.

DOI:10.34219/2078-8320-2023-14-5-7-14