ОБЗОР АЛГОРИТМОВ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ГРАФАХ

REVIEW OF THE FIDING SHORTEST PATHS IN GRAPHS ALGORITHMS

Natalia Vasileva

PhD student, Far Eastern Federal University

Russia, Vladivostok

АННОТАЦИЯ

Проведен анализ понятия кратчайший путь в графе, рассмотрены основные алгоритмы поиска кратчайших путей в графе с указанием ограничений по применению и временной сложности реализации алгоритма

ABSTRACT

The concept of the shortest path in a graph was analyzed, the main algorithms for the shortest paths in a graph searching were considered, restrictions on the application and time complexity of the algorithms’ implementation were indicated

Ключевые слова: алгоритм поиска кратчайшего пути, поиск кратчайшего пути в графе, алгоритм Дейкстры, алгоритм Флойда-Уоршелла, алгоритм А*, алгоритм Джонсона, алгоритм Данцига, алгоритм APSP-RET, алгоритм Беллмана-Форда, Генетический, алгоритм поиска в ширину, алгоритм топологической сортировки

Keywords: shortest path algorithm, shortest path search in a graph, Dijkstra algorithm, Floyd-Warshell algorithm, A* algorithm, Johnson algorithm, Danzig algorithm, APSP-RET algorithm, Bellman-Ford algorithm, Genetic, breadth-first search algorithm, topological sorting algorithm

Понятие кратчайшего пути в графе, по мнению ученых, может быть объединено следующим образом: кратчайший путь в графе - это простой путь между двумя вершинами графа с наименьшей стоимостью. Однако, ученые различают критерий наименьшей стоимости. Множество ученых, среди которых М. Харари, Н. Вирт, Р. Седжвик, М. Гудрич [1, с. 67; 2, с. 88; 3, с. 212; 4, с. 194] употребляют понятия «наименьшая стоимость», «наименьший путь», «наименьшая длина», «минимальное расстояние», которые могут быть уточнены при решении практических задач. Более точны Д. Вест и Д. Кнут [5, с. 144;6, с. 152], которые под наименьшей стоимостью предполагают наименьшую сумму весов ребер, а значит, определение кратчайшего пути во взвешенных графах, что сокращает область применения понятия. Также, как и в случае с определениями Т. Кормена [7, с. 729], которые под стоимостным критерием понимают мощность ребер в множестве вершин, входящих в кратчайший путь. Таким образом, целесообразно для определения понятия кратчайшего пути во взвешенных графах применять понятие Д. Веста и Д. Кнута, а в невзвешенных графах – понятие Т. Кормена.

Для нахождения кратчайших путей в графе разработаны различные алгоритмы поиска кратчайших путей. Наиболее известные из них: алгоритм Дейкстры, алгоритм Флойда-Уоршелла, алгоритм А*, алгоритм Джонсона, алгоритм Данцига, алгоритм APSP-RET, алгоритм Беллмана-Форда, Генетический, алгоритм поиска в ширину, алгоритм топологической сортировки и др.

Каждый из этих алгоритмов обладают своими особенности и могут быть эффективно применены в различных прикладных задачах. Например, данные алгоритмы активно используются в программировании игр при проектировании игровой механики для прохождения персонажами игровых карт, при решении транспортных задач перемещения пассажиров или грузов на графе города по кратчайшим маршрутам, при решении задач из области сетевого планирования для оптимизации управленческих решений, а также для анализа структуры социальных сетей (выявления лидеров общественных мнений и установления кратчайших каналов связи между ними за счет общих акторов сети) и др.

Однако, стоит отметить, что каждый алгоритм, рассмотренный в данной статье, обладает своими особенностями вычислений, сложностью и принципом работы, отличающим его от других.

Основные характеристики рассматриваемых алгоритмов представлены далее.

1. Алгоритм Дейкстры (1959, Эдсгер Дейкстра) предназначен для нахождения кратчайшего пути от одной вершины до всех остальных вершин во взвешенном ориентированном графе без рёбер отрицательного веса. Алгоритм работает пошагово, обновляя расстояния до вершин, пока не будет найден кратчайший путь до каждой вершины.   Сложность: O(n^2). Работает только с графами без рёбер отрицательного веса [7, p. 658-662].
2. Алгоритм Флойда-Уоршелла (1962, Роберт Флойд, Стивен Уоршелл). Алгоритм строит матрицу расстояний, где каждый элемент - это длина кратчайшего пути между соответствующими вершинами.     Сложность: O(n^3). Работает между всеми парами вершин во взвешенном ориентированном графе с возможным наличием ребер отрицательного веса [7, p. 695-698].
3. Алгоритм Данцига (1956, Джордж Данциг) итеративном обновлении кратчайших путей посредством релаксации ребер.     Сложность: O(n^3). Работает между всеми парами вершин во взвешенном ориентированном графе с возможным наличием ребер отрицательного веса [8, с. 181-184].
4. Алгоритм А* (1968, Питер Харт, Нильс Нильсон, Бертрам Раппапорт) работает с использованием эвристической функции, оценивающей расстояние до целевой вершины. Алгоритм комбинирует информацию о предыдущих путях с использованием эвристической функции для выбора оптимального следующего шага.  сложности в зависимости от выбора эвристической функции и структуры графа. Работает только для поиска кратчайшего пути от одной вершины до другой конечной вершины [9, p. 78-80].
5. Алгоритм Джонсона (1977, Дональд Джонсон) модифицирует граф, добавляя фиктивную вершину и рассчитывая новые веса ребер, а затем применяет алгоритм Дейкстры или алгоритм Беллмана-Форда.        Сложность: O(n^2 * log(n) + nm).         Работает между всеми парами вершин во взвешенном ориентированном графе с возможным наличием ребер отрицательного веса, но без отрицательных циклов [7, p. 660-664].
6. Алгоритм APSP-RET (All Pairs Shortest Paths - Reduce, Evaluate, Truncate) (1993, Д. Жижунг, М. Ф. Тарабин, Дж. Давидсон, М. Марак)   работает на основе идей динамического программирования. Алгоритм состоит из трех основных этапов: уменьшения размерности графа, вычисления кратчайших путей и обрезания. Сложность: O(n^2 * m). Производит поиск всех кратчайших путей между всеми парами вершин в графе [10].
7. Алгоритм Беллмана-Форда (1958, Ричард Беллман, Лестер Форд) выполняет релаксацию всех ребер графа для каждой вершины в графе n-1 раз, где n - количество вершин в графе. Алгоритм постепенно улучшает предполагаемые расстояния до вершин, пока не найдет оптимальное решение. Сложность: O(n* m).         Применяется при поиске кратчайшего пути в том числе и во взвешенных, ориентированных графах и графах с отрицательными весами ребер [11].
8. Генетический алгоритм (1960, Джон Холланд) основан на принципах естественного отбора и генетики. Алгоритм моделирует процесс эволюции, в котором популяция особей размножается и эволюционирует с помощью операторов скрещивания и мутации. Каждая особь представляет собой потенциальное решение, и эволюция позволяет находить оптимальное решение путем последовательного улучшения поколения. в зависимости от размера популяции, количества поколений и операторов скрещивания и мутации. Обычно оценивается как O(G * P * (C + O)), где G - количество поколений, P - размер популяции, C - сложность оценки приспособленности особи, O - сложность операторов скрещивания и мутации. Ограничения и характеристики графов зависят от специфической задачи и условий применения алгоритма [12, 13].
9. Алгоритм Поиска в ширину (1959, Эдвард Форест Мур) начинает с заданной вершины и постепенно расширяет область поиска на все ближайшие к текущей вершине. В процессе работы алгоритма строится дерево поиска, в котором каждая вершина имеет указатель на своего предка. Кратчайший путь можно восстановить, пройдя по указателям от конечной вершины до начальной. Сложность: O(n + m). Работает только в невзвешенном графе [3, 7].
10. Топологической алгоритм сортировки (1957, Артур Кан)   работает путем выбора вершины без входящих ребер и удаления ее из графа. Полученная последовательность вершин является топологической сортировкой графа. Алгоритм может быть использован для решения задач, требующих последовательного выполнения. O(n + m)     в ориентированном ациклическом графе, только к ориентированным ациклическим графам [3, 7].

Рассмотренные алгоритмы обладают характерными особенностями и различной вычислительной сложностью в зависимости от логики работы алгоритма. Однако, у алгоритмов с наименьшей сложностью также существуют существенные ограничения по применению на графовых структурах. А универсальные алгоритмы предполагают высокую стоимость реализации. Таким образом, существует необходимость дальнейшего исследования этого вопроса, в том числе, по категоризации задач для дальнейшего применения соответствующего алгоритма, требующего минимальной стоимости при решении определенных практических задач.

Список литературы:

1. Харари Ф. Теория графов. Пер. с англ. Изд. 6, URSS, 2022. 304 с.
2. Никлаус Вирт. Алгоритмы и структуры данных. Новая версия для Оберона + CD / Пер. с англ. Ткачев Ф. В. М.: ДМК Пресс, 2010. 272 с.: ил.
3. Седжвик, Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер с англ. / Р. Седжвик. СПб: ООО «ДиаСофтЮП», 2002. 496 с.
4. Гудрич М.Т. , Тамассия Р. Структуры данных и алгоритмы в Java. Новое знание, 2003. 671 с.
5. Douglas Brent West. Introduction to Graph Theory Subsequent Edition. Pearson College Div; Subsequent edition, 2000. 588 p.
6. Дональд Кнут, Рональд Л. Грэхем, Орен Паташник. Конкретная математика. Математические основы информатики. Вильямс. 2010. 784 с.
7. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, third edition. MIT Press, 2009. 1320 p.
8. Дасгупта С. и др. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани; Пер. с англ. под ред. А. Шеня. М.: МЦНМО, 2014. 320 с.
9. David L. Poole, Alan K. Mackworth. Artificial Intelligence: Foundations of Computational Agents. Cambridge University Press, 2010 г. 662 p.
10. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs // Theor. Comput. Sci., 312(1):47–74, 2004.
11. Ford, L.R., Fulkerson, D.R. Constructing Maximum-Weight Binary Trees and Binary Sequential Automata. Journal of the ACM, 1958. p. 347-354.
12. Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison. Wesley Professional, 1989. 412 p.
13. Holland, J.H. Adaptation in Natural and Artificial Systems. MIT Press, 1992. 232 p.