Как найти кратчайший путь между точками - Сайт, где вы сможете решить свои вопросы

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 20 августа 2021 года; проверки требуют 7 правок.

Кратчайший путь (A, B, D, F) между вершинами A и F в неориентированном графе без весов.

Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе.

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

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для её решения^[⇨].

У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.

Значимость данной задачи определяется её различными практическими применениями^[⇨]. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между точкой отправления и точкой назначения. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Если сумма длин дорог между перекрёстками минимальна, тогда найденный путь самый короткий.

Определение[править | править код]

Задача поиска кратчайшего пути на графе может быть определена для неориентированного, ориентированного или смешанного графа. Далее будет рассмотрена постановка задачи в самом простом виде для неориентированного графа. Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.

Граф представляет собой совокупность непустого множества вершин и рёбер (наборов пар вершин). Две вершины на графе смежны, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин $P=(v_{1},v_{2},ldots ,v_{n})in Vtimes Vtimes ldots times V$ , таких что $v_{i}$ смежна с $v_{{i+1}}$ для . Такой путь называется путём длиной из вершины $v_{1}$ в $v_{n}$ ( указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).

Пусть $e_{{i,j}}$ — ребро соединяющее две вершины: $v_{i}$ и $v_{j}$ . Дана весовая функция , которая отображает ребра на их веса, значения которых выражаются действительными числами, и неориентированный граф . Тогда кратчайшим путём из вершины в вершину будет называться путь $P=(v_{1},v_{2},ldots ,v_{n})$ (где $v_{1}=v$ и $v_{n}=v'$ ), который имеет минимальное значение суммы $sum _{{i=1}}^{{n-1}}f(e_{{i,i+1}}).$ Если все ребра в графе имеют единичный вес, то задача сводится к определению наименьшего количества обходимых ребер.

Существуют различные постановки задачи о кратчайшем пути:

Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объём затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).

Задача о кратчайшем пути с учётом дополнительных ограничений[править | править код]

Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи^[1]. Примеры таких задач:

Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теории исследования операций^[2].
Минимальное покрытие вершин ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути^[3].
Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей $P={p_{1},dots ,p_{m}}$ такое, что для любого $t_{i}in R$ найдется путь $p_{j}in P$ , накрывающий его. $R={t_{1},dots ,t_{k}}$ — множество некоторых путей в ориентированном графе G^[4].
Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмножества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины^[5].

Алгоритмы[править | править код]

В связи с тем, что существует множество различных постановок данной задачи, есть
наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе:

Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса^[6].
Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес рёбер может быть отрицательным.
Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа^[6].
Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (рёбер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Также используется для поиска кратчайшего расстояния на карте в стратегических играх.
Поиск кратчайшего пути на основе алгоритма Килдала^[7].

В работе (Черкасский и др., 1993)^[8] представлено ещё несколько алгоритмов для решения этой задачи.

Задача поиска кратчайшего пути из одной вершины во все остальные[править | править код]

В такой постановке задачи осуществляется поиск кратчайшего пути из вершины v во все остальные вершины на графе.

Невзвешенный ориентированный граф[править | править код]

Алгоритм	Сложность	Автор
Поиск в ширину	O(V+E)

Ориентированный граф с неотрицательными весами[править | править код]

Алгоритм	Сложность	Автор
–	O(V²EL)	Форд 1956
Алгоритм Беллмана — Форда	O(VE)	Беллман 1958^[9], Мур 1957^[10]
–	O(V² log V)	Данциг 1958, Данциг 1960, Minty (cf. Pollack&Wiebenson 1960), Whiting&Hillier 1960
Алгоритм Дейкстры со списком.	O(V²)	Leyzorek et al. 1957^[11], Дейкстра 1959^[12]
Алгоритм Дейкстры с модифицированной двоичной кучей	O((E + V) log V)	–
. . .	. . .	. . .
Алгоритм Дейкстры с использованием фибоначчиевой кучи	O(E + V log V)	Фридман&Тарьян 1984^[13], Фридман&Тарьян 1987^[14]
–	O(E log log L)	Джонсон 1982, Карлссон&Поблете 1983
Алгоритм Габова	O(E log_E/V L)	Габов 1983, Габов 1985
–	O(E + V√log L)	Ахуджа et al. 1990

Ориентированный граф с произвольными весами[править | править код]

Алгоритм	Сложность	Автор
Алгоритм Беллмана — Форда	O(VE)	Беллман^[9], Мур^[10]
Алгоритм Левита	O(VE)

Задача о кратчайшем пути между всеми парами вершин[править | править код]

Задача о кратчайшем пути между всеми парами вершин для невзвешенного ориентированного графа была поставлена Симбелом в 1953 году^[15], который обнаружил, что она может быть решена за линейное количество манипуляций (умножения) с матрицей. Сложность такого алгоритма O(V⁴).

Так же для решения данной задачи существуют другие более быстрые алгоритмы, такие как Алгоритм Флойда — Уоршелла со сложностью O(V³), и
Алгоритм Джонсона (является комбинацией алгоритмов Бэллмана-Форда и Дейкстры) со сложностью O(VE + V² log V).

Применение[править | править код]

Задача о поиске кратчайшего пути на графе может быть интерпретирована по-разному и применяться в различных областях. Далее приведены примеры различных применений задачи. Другие применения изучаются в дисциплине, которая занимается исследованием операций^[16].

Картографические сервисы[править | править код]

Алгоритмы нахождения кратчайшего пути на графе применяются для нахождения путей между физическими объектами на таких картографических сервисах, как карты Google или OpenStreetMap. В обучающем видео от Google можно узнать различные эффективные алгоритмы, которые применяются в данной сфере^[17].

Недетерминированная машина[править | править код]

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

Сети дорог[править | править код]

Задача поиска кратчайшего пути на графе широко используется при определении наименьшего расстояния в сети дорог.

Сеть дорог можно представить в виде графа с положительными весами. Вершины являются дорожными развязками, а ребра дорогами, которые их соединяют. Веса рёбер могут соответствовать протяжённости данного участка, времени необходимому для его преодоления или стоимости путешествия по нему. Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например автомагистрали). Она была формализована в понятии (идее) о магистралях^[18].

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

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

Самый быстрый алгоритм может решить данную задачу на дорогах Европы или Америки за доли микросекунды^[19].

Другие подходы (техники), которые применяются в данной сфере:

ALT
Arc Flags
Contraction hierarchies
Transit Node Routing
Reach based Pruning
Labeling

Постановка задачи линейного программирования[править | править код]

Пусть дан направленный граф (V, A), где V — множество вершин и A — множество рёбер, с начальной вершиной обхода s, конечной t и весами w_ij для каждого ребра (i, j) в A. Вес каждого ребра соответствует переменной программы x_ij.

Тогда задача ставится следующим образом: найти минимум функции $F=sum _{{ijin A}}w_{{ij}}x_{{ij}}$ , где $x_{{ij}}geq 0$ , при условии что для всех i и j выполняется следующее неравенство: $sum _{j}x_{{ij}}-sum _{j}x_{{ji}}={begin{cases}1,&{text{if }}i=s;\-1,&{text{if }}i=t;\0,&{text{ otherwise.}}end{cases}}$

См. также[править | править код]

IEEE 802.1aq
Транспортная сеть
Двунаправленный поиск

Примечания[править | править код]

↑ Применение теории графов в программировании, 1985.
↑ Применение теории графов в программировании, 1985, с. 138—139.
↑ Применение теории графов в программировании, 1985, с. 139—142.
↑ Применение теории графов в программировании, 1985, с. 144—145.
↑ Применение теории графов в программировании, 1985, с. 145—148.
↑ ¹ ² Дискретная математика. Комбинаторная оптимизация на графах, 2003.
↑ Применение теории графов в программировании, 1985, с. 130—131.
↑ Cherkassky, Goldberg, Radzik, 1996.
↑ ¹ ² Bellman Richard, 1958.
↑ ¹ ² Moore, 1957.
↑ M. Leyzorek, 1957.
↑ Dijkstra, 1959.
↑ Michael Fredman Lawrence, 1984.
↑ Fredman Michael, 1987.
↑ Shimbel, 1953.
↑ Developing algorithms and software for geometric path planning problems, 1996.
↑ Fast route planning.
↑ Highway Dimension, 2010.
↑ A Hub-Based Labeling Algorithm, 2011.
↑ Ladyzhensky Y., Popoff Y. Algorithm, 2006.

Литература[править | править код]

Евстигнеев В. А. Глава 3. Итеративные алгоритмы глобального анализа графов. Пути и покрытия // Применение теории графов в программировании / Под ред. А. П. Ершова. — Москва: Наука. Главная редакция физико-математической литературы, 1985. — С. 138—150. — 352 с.
Алексеев В.Е., Таланов В.А. Глава 3.4. Нахождения кратчайших путей в графе // Графы. Модели вычислений. Структуры данных. — Нижний Новгород: Издательство Нижегородского гос. университета, 2005. — С. 236—237. — 307 с. — ISBN 5–85747–810–8. Архивная копия от 13 декабря 2013 на Wayback Machine
Галкина В.А. Глава 4. Построение кратчайших путей в ориентированном графе // Дискретная математика. Комбинаторная оптимизация на графах. — Москва: Издательство “Гелиос АРВ”, 2003. — С. 75—94. — 232 с. — ISBN 5–85438–069–2.
Берж К. Глава 7. Задача о кратчайшем пути // Теория графов и её применения = Theorie des graphes et ses applications / Под ред. И. А. Вайнштейна. — Москва: Издательство иностранной литературы, 1962. — С. 75—81. — 320 с.
Ойстин Оре. Теория графов / Под ред. И. М. Овчинниковой. — Издательство наука, 1980. — 336 с. Архивная копия от 15 декабря 2013 на Wayback Machine
Виталий Осипов, Поиск кратчайших путей в дорожных сетях: от теории к реализации на YouTube.
Харари Ф. Глава 2. Графы // Теория графов / под ред. Г. П. Гаврилов — М.: Мир, 1973. — С. 27. — 301 с.
Cherkassky B. V., Goldberg A. V., Radzik T. Shortest paths algorithms: Theory and experimental evaluation (англ.) // Mathematical Programming — Springer Science+Business Media, 1996. — Vol. 73, Iss. 2. — P. 129–174. — ISSN 0025-5610; 1436-4646 — doi:10.1007/BF02592101
Ричард Беллман. On a routing problem // Quarterly of Applied Mathematics. — 1958. — Т. 16. — С. 87—90.
Dijkstra E. W. A note on two problems in connexion with graphs (англ.) // Numerische Mathematik / F. Brezzi — Springer Science+Business Media, 1959. — Vol. 1, 1, Iss. 1, 1. — P. 269—271, 269—271. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF01386390
Moore E. F. The shortest path through a maze (англ.) // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957) — Harvard University Press, 1959. — Vol. 2. — P. 285—292. — 345 p. — (Annals of the Computation Laboratory of Harvard University; Vol. 30) — ISSN 0073-0750
M. Leyzorek, R. S. Gray, A. A. Gray, W. C. Ladew, S. R. Meaker, R. M. Petry, R. N. Seitz. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems (англ.). — Cleveland, Ohio: Case Institute of Technology, 1957.
Michael Fredman Lawrence, Роберт Андре Тарьян. Fibonacci heaps and their uses in improved network optimization algorithms (англ.) : journal. — Институт инженеров электротехники и электроники, 1984. — P. 338—346. — ISBN 0-8186-0591-X. — doi:10.1109/SFCS.1984.715934. Архивировано 11 октября 2012 года.
Michael Fredman Lawrence, Роберт Андре Тарьян. Fibonacci heaps and their uses in improved network optimization algorithms (англ.) // Journal of the Association for Computing Machinery : journal. — 1987. — Vol. 34, no. 3. — P. 596—615. — doi:10.1145/28869.28874.
Shimbel, Alfonso. Structural parameters of communication networks // Bulletin of Mathematical Biophysics. — 1953. — Т. 15, № 4. — С. 501—507. — doi:10.1007/BF02476438.
Sanders, Peter. Fast route planning. — Google Tech Talk, 2009. — 23 марта.. — «Шаблон:Inconsistent citations».
Chen, Danny Z. Developing algorithms and software for geometric path planning problems (англ.) // ACM Computing Surveys (англ.) (рус. : journal. — 1996. — December (vol. 28, no. 4es). — P. 18. — doi:10.1145/242224.242246.
Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms (англ.) // ACM-SIAM Symposium on Discrete Algorithms : journal. — 2010. — P. 782—793.
Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks. Symposium on Experimental Algorithms] (англ.) : journal. — 2011. — P. 230—241.
Kroger, Martin. Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems (англ.) // Computer Physics Communications (англ.) (рус. : journal. — 2005. — Vol. 168, no. 168. — P. 209—232. — doi:10.1016/j.cpc.2005.01.020.
Ladyzhensky Y., Popoff Y. Algorithm to define the shortest paths between all nodes in a graph after compressing of two nodes. Proceedings of Donetsk national technical university, Computing and automation. Vol.107. Donetsk (англ.) : journal. — 2006. — P. 68—75..^{[источник не указан 920 дней]}

Источник

Алгоритм Дейкстры. Разбор Задач

Время на прочтение
7 мин

Количество просмотров 34K

Поиск оптимального пути в графе. Такая задача встречается довольно часто и в повседневной жизни, и в мире технологий. Справиться с такими вызовами помогает подход, который должен быть в арсенале каждого программиста — алгоритм Дейкстры.

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

Введение

Алгоритм Дейкстры работает на ориентированных (с некоторыми дополнениями и на неориентированных) графах, и призван искать кратчайшие пути между заданной вершиной и всеми остальными вершинами в графе.

Как правило, граф обозначают как набор вершин и рёбер где число рёбер может быть задано , а вершин числом

Для каждого ребра в графе задан неотрицательный вес , а также вершина, из которой осуществляется поиск оптимальных путей.

Алгоритм Дейкстры может найти кратчайший путь между вершинами и в графе, только если существует хотя бы один путь между этими вершинами. Если это условие не выполняется, то алгоритм отработает корректно, вернув значение “бесконечность” для пары несвязанных вершин.

Условие неотрицательности весов рёбер крайне важно и от него нельзя просто избавиться. Не получится свести задачу к решаемой алгоритмом Дейкстры, прибавив наибольший по модулю вес ко всем рёбрам. Это может изменить оптимальный маршрут. На рисунке видно, что в первом случае оптимальный путь между и (сумма рёбер на пути наименьшая) изменяется при такой манипуляции. В оригинале путь проходит через , а после добавления семёрки ко всем рёбрам, оптимальный путь проходит через

Как ведёт себя алгоритм Дейкстры на исходном графе, мы разберём, когда выпишем алгоритм. Но для начала зададимся другим вопросом: “почему не применить поиск в ширину для нашего графа?”. Известно, что метод BFS находит оптимальный путь от произвольной вершины в ориентированном графе до любой другой вершины, но это справедливо только для рёбер с единичным весом.

Свести задачу к решаемой BFS можно, но если заменить все рёбра неединичной длины рёбрами длины , то граф очень разрастётся, и это приведёт к огромному числу действий при вычислении оптимального маршрута.

Чтобы этого избежать предлагается использовать алгоритм Дейкстры. Опишем его:

Инициализация:

Основный цикл алгоритма:

Пока все вершины не исследованы (или формально ), повторяем:

В итоге исполнения этого алгоритма, массив будет содержать все оптимальные пути, исходящие из .

Примеры работы

Рассмотрим граф выше, в нём будем искать пути от до всего остального.

Первый шаг алгоритма определит, что кратчайший путь до проходит по направлению синей стрелки и зафиксирует кратчайший путь. Второй шаг рассмотрит, все возможные варианты $inline A[v] + l_{vw}$ и окажется, что оптимальный вариант двигаться вдоль красной стрелки, поскольку меньше, чем и Добавляется длина кратчайшего пути до . И наконец, третьим шагом, когда три вершины уже лежат в , остается рассмотреть только два ребра и выбрать, лежащее вдоль зеленой стрелки.

Теперь рассмотрим граф с отрицательными весами, упомянутый выше. Напомню, алгоритм Дейкстры на таком графе может работать некорректно.

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

Оценка сложности алгоритма

К этому моменту мы разобрали сам алгоритм, ограничения, накладываемые на его работу и ряд примеров его применения. Давайте упомянем какова вычислительная сложность этого алгоритма, поскольку это пригодится нам для решения задач, ради которых затевалась эта статья.
Базовый подход, основанный на циклах, предполагает проход по всем рёбрам каждого узла, что приводит к сложности .

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

Что еще можно сказать о куче:

это сбалансированное бинарное дерево,
ключ текущего узла всегда меньше, либо равен ключей дочерних узлов.

Интересную задачу с использованием куч я разбирал ранее в этом посте.

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

Далее перейдём к разбору задач!

Задача №1

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

Решение

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

В случае классической задачи, поиска пути минимальной длины между двумя вершинами графа, мы поддерживаем в каждой посещенной алгоритмом вершине графа минимальную длину пути до этой вершины. Здесь стоит оговориться, что будем именовать множество посещенными вершинами, а V - X часть графа, для которой еще нужно найти величину пути или узкого места.

В отличии от классического алгоритма, решение этой задачи должно поддерживать величину актуального узкого места пути, приводящего в вершину v in X . А при добавлении новой вершины из V - X , мы должны смотреть не увеличивает ли ребро (v,u_1) величину узкого места пути, которое теперь приводит в u_1 .
Если ребро увеличивает узкое место, то лучше рассмотреть вершину u_2 , ребро до которой легче (v,u_1) . Поиск неувеличивающих узкое место ребёр нужно осуществлять не только среди соседей определенного узла , но и среди всех v in X , поскольку отдавая предпочтение вершине, путь в которую имеет наименьшее узкое место в данный момент, мы гарантируем, что мы не ухудшаем ситуацию для других вершин.

Последнее можно проиллюстрировать примером: если путь, оканчивающийся в вершине имеет узкое место величины , и есть вершина с ребром (p,q) веса , и с ребром (p,r) веса , то предпочтение отдаётся , алгоритм даст верный результат в обоих случая, если существует (q,r) веса или веса .

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

$A(u) = min_{v in X}left(max left[A(v), wleft(v,uright)right]right), , u in V - X$

Стоит пояснить, что поиск по v in X осуществляется, только для существующих связей (v,u), а это вес ребра (v,u) .

Задача №2

Предлагается решить более практическую задачу. Пусть городов, между ними существуют пути, заданные массивом edges[i] = [city_a, city_b, distance_ab], а также дано целое число mileage.

Требуется найти такой город из данных, из которого можно добраться до наименьшего числа городов не превысив mileage.

Стоит отметить, что граф неориентированый, т.е. по пути между городами можно двигаться в обе стороны, а длина пути между городами a и c может быть получена как сумма длин путей a -> b и b -> c, если есть маршрут a -> b -> c

Решение

С решением данной проблемы нам поможет алгоритм Дейкстры и описанная выше реализация с помощью кучи. Поставщиком этой структуры данных станет библиотека heapq в Python.

Будем использовать алгоритм Дейкстры для того, чтобы подсчитать количество соседних городов, расстояние до которых меньше mileage, для каждого из городов. Соберем количества соседей в в одном месте и найдем минимум из них.

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

Давайте опишем функцию решения:

def least_reachable_city(n, edges, mileage):
        """
        входные параметры:
            n --- количество городов,
            edges --- тройки (a, b, distance_ab),
            mileage --- максимально допустимое расстояние между городами 
            для соседства
        """
        # заполняем список смежности (adjacency list), в нашем случае это 
        # словарь, в котором ключи это города, а значения --- пары 
        # (<другой_город>, <расстояние_до_него>)

        graph = {}
        for u, v, w in edges:
            if graph.get(u, None) is None:
                graph[u] = [(v, w)]
            else:
                graph[u].append((v, w))
            if graph.get(v, None) is None:
                graph[v] = [(u, w)]
            else:
                graph[v].append((u, w))
        
        # локально объявим функцию, которая будет считать кратчайшие пути в 
        # графе от вершины, до всех вершин, удовлетворяющих условию
        def num_reachable_neighbors(city):
            # создаем кучу, из одного элемента с парой, задающей нулевую 
            # длину пути до самого исходного города
            heap = [(0, city)]
            # и массив, содержащий города и кратчайшие 
            # расстояния до них от исходного
            distances = {}
            # затем, пока куча не пуста, извлекаем ближайший 
            # от посещенных городов город
            while heap:
                currDist, neighb = heapq.heappop(heap)
                # если кратчайшее ребро ведет к городу, где мы уже знаем 
                # оптимальный маршрут, то завершаем итерацию
                if neighb in distances:
                    continue
                # в остальных случаях, и если сосед не является отправным 
                # городом, мы добавляем новую запись в массив кратчайших расстояний
                if neighb != city:    
                    distances[neighb] = currDist
                # обрабатываем всех смежных городов с соседом, добавляя их в кучу 
                # но только если: а) до них еще не известен кратчайший маршрут и б) путь до них через neighb не выходит за пределы mileage
                for node, d in graph[neighb]:
                    if node in distances:
                        continue
                    if currDist + d <= mileage:
                        heapq.heappush(heap, (currDist + d, node))
            # возвращаем количество городов, прошедших проверку
            return len(distances)
        
        # выполним поиск соседей для каждого из городов
        cities_neighbors = {num_reachable_neighbors(city): city for city in range(n)}
        # вернём номер города, у которого наименьшее число соседей
        # в пределах досигаемости
        return cities_neighbors[min(cities_neighbors)]

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

Заключение

Алгоритм Дейкстры это мощный инструмент в мире работы с графами, область применения его крайне широка. С его помощью можно оценить даже целесообразность добавления новой ветки метро, новой дороги или маршрута в компьютерной сети. Он прост в исполнении и интуитивно понятен, как другие жадные (greedy) алгоритмы. Вычислительная сложность решений задач с его помощью зачастую не выше . При некоторых условиях может достигать линейной сложности (существует алгоритм линейной сложности, решающий первую задачу, при условии, что граф неориентированный).

Стоит еще раз отметить, что алгоритм не работает, когда в графе существуют отрицательные веса. Для этого существует подход динамического программирования — алгоритм Беллмана – Форда, что может послужить темой другой статьи. Несмотря на это, алгоритм Дейкстры является представителем идеального баланса простоты и мощи, для решения прикладных задач.

Статья подготовлена в преддверии старта курса «Алгоритмы для разработчиков». Узнать о курсе подробнее, а также зарегистрироваться на бесплатный демоурок можно по ссылке.

Информация

[1] Условия задач взяты из книги «Algorithms Illuminated: Part 2: Graph Algorithms and Data Structures» от Tim Roughgarden,
[2] и с сайта leetcode.com.
[3] Решения авторские.

Источник

Алгоритм Дейкстры — это метод, который находит кратчайший путь от одной вершины графа к другой. Граф — структура из точек-вершин, соединенных ребрами-отрезками. Его можно представить как схему дорог или как компьютерную сеть. Ребра — это связи, по ним можно двигаться от одной вершины к другой.

Графы используют для моделирования реальных объектов, а алгоритмы поиска пути — при их изучении, а также решении практических задач. Алгоритм Дейкстры работает для графов, у которых нет ребер с отрицательным весом, т.е. таких, при прохождении через которые длина пути как бы уменьшается.

В отличие от похожих методов, алгоритм Дейкстры ищет оптимальный маршрут от одной заданной вершины ко всем остальным. Попутно он высчитывает длину пути — суммарный вес ребер, по которым проходит при этом маршруте.

Кто пользуется алгоритмом Дейкстры

Математики и другие ученые, которые пользуются графами как абстрактными единицами. Задача поиска маршрута в науке может быть и чисто фундаментальной, и прикладной.
Дата-сайентисты. В этой области много математики, в том числе активно используется теория графов.
Сетевые инженеры, так как алгоритм Дейкстры лежит в основе работы нескольких протоколов маршрутизации. Сама по себе компьютерная сеть представляет собой граф, поэтому специалисты по сетям должны знать, что это такое.

Зачем нужен алгоритм Дейкстры

Основная задача — поиск кратчайшего пути по схеме, где множество точек соединено между собой отрезками. В виде такой схемы можно представить многие объекты реального мира, поэтому практических примеров использования алгоритма много:

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

Как работает алгоритм

Алгоритм Дейкстры пошаговый. Сначала выбирается точка, от которой будут отсчитываться пути. Затем алгоритм поочередно ищет самые короткие маршруты из исходной точки в другие. Вершины, где он уже побывал, отмечает посещенными. Алгоритм использует посещенные вершины, когда рассчитывает пути для непосещенных.

Это может звучать сложно, поэтому мы хотим показать вам, как это выглядит на примере. Возьмем такой граф: цифрами в кружках обозначены вершины, а числа возле ребер — это вес путей между ними.

Инициализация. Пусть вершиной, из которой мы будем считать маршруты, будет 0. Расстояние до самой себя у этой вершины логично равно нулю. Остальные мы пока не знаем, поэтому отметим символом бесконечности.

Расстояние от 0 до 0 помечаем равным нулю, а саму вершину — посещенной.

Первый шаг алгоритма. Мы выбираем еще не посещенную вершину с самой маленькой меткой относительно исходной — то есть такую, которая находится ближе всех. На первом шаге это одна из соседних вершин — та, которая соединена с исходной самым «маленьким» ребром.

Для графа, который мы рассматриваем, это точка 2. Мы выбираем ее, «переходим» в нее и смотрим уже на ее соседей.

Дальнейшие шаги алгоритма. Для выбранной точки нужно осмотреть соседей и записать длину пути до них с учетом пройденного пути. А потом выбрать ближнюю точку. Но есть нюанс: нужно учитывать точки, которые мы уже использовали в прошлый раз. Если они дают более «выгодный» путь, лучше воспользоваться ими.

Например, на выбранном графе есть точка 1. В нее можно перейти из точки 2, где мы находимся. Но этот путь будет длиннее, чем при переходе напрямую из точки 0, а ведь она для нас исходная. Поэтому «короткий путь» для точки 1 — это маршрут 0–1. Отмечаем вершину посещенной.

Шаги повторяются, пока на графе есть непосещенные точки. Если вершину не посетили, она не участвует в расчетах. Если после ее «открытия» появился новый, более короткий путь к какой-либо точке, то минимальное расстояние для нее перезаписывается.

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

Мы говорим «длина», но это условно. Например, при поиске билетов в роли веса ребра может выступать их цена, а при организации электрической цепи — расход электроэнергии.

Теория графов — обширная отрасль дискретной математики. Ее используют во множестве сфер, от химии до разработки. В профильных университетах теорию графов изучают на курсе дискретной математики. Также получить базу знаний и решать практические задачи под контролем наставника можно на курсах SkillFactory.

Источник

6.1. Нахождение кратчайшего пути

Задача нахождения кратчайшего пути
имеет две формулировки:

• найти кратчайший разомкнутый путь;

• найти кратчайший замкнутый путь.

Для решения каждого варианта задачи
созданы специальные алгоритмы.
Наибольший интерес представляет задача
о поиске кратчайшего замкнутого пути,
при условии, что требуется посетить все
указанные пункты маршрута хотя бы по 1
разу.

6.1.1. Прямой симметричный алгоритм

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

Пример 1.
Проложить водопроводные
трубы между девятью объекта кратчайшим
(в экономическом смысле) путем. Объект
0 —
водонапорная башня. Данные приведены
на рисунке, где на ребрах графа —
стоимость работ по прокладке водопровода
на данном участке (ребре).

Рис.1

Введем следующие обозначения.

dj
— стоимость работ по
прокладке водопровода между объетами
i
и j.

Qj
— минимальная стоимость
работ от объекта 0 до
объекта, т.е. Qо
= 0.

Тогда Qj
= min(Q_j
+ c_ij).

Будем иметь:

Минимальная стоимость прокладки
водопровода между пунктами

0 и 8
составит 2 + 2 + 4 = 8 и
пройдет по маршруту 0-1-4-8

Рис.2

Минимальная стоимость прокладки
водопровода между всеми пунктами
составит: 2 + 2 + 4 + 3 + 2 + 3 + 2 + 3 = 21. Схема
прокладки водопровода, соединяющего
все пункты, представлена.

Рис.3

6.1.2. Задача коммивояжера

Задача коммивояжера имеет
длинную историю. Во времена расцвета
Британской империи (захвата колоний и
географических открытий) англичанин
У. Гамильтон придумал новую игру, суть
которой состоит в том, что необходимо
посетить все указанные города и вернуться
назад. Такой замкнутый цикл (точка старта
является и точкой финиша) называют
гамильтоновым циклом.
Впоследствии задача Гамильтона была
уточнена и указаны пути ее решения
математиками Г. Лейбницем и Я. Бернулли.

В современной интерпретации
задача коммивояжера формулируется
так:

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

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

Математическая модель задачи коммивояжера
имеет вид:

(6.1)

где п
– количество вершин
замкнутого графа;

С_ij
расстояние между городами (затраты
ресурса между

работами) при наложенных ограничениях:

C_ij>
0 — расстояния (ресурсы) не отрицательны;

Cjj
= °° — запрет на
петли внутри маршрута;

Cij
= Cji
—принцип симметричности
(расстояние между городами одинаковое);

Cij
+ Cjk≥Cik
—принцип треугольника
(в город короче проехать напрямую,
чем через третий город).

Существует масса разновидностей
обобщённой постановки задачи, в частности
геометрическая задача коммивояжёра
(когда матрица расстояний отражает
расстояния между точками на плоскости),
треугольная задача коммивояжёра (когда
на матрице стоимостей выполняется
неравенство треугольника), симметричная
и асимметричная задачи коммивояжёра.

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

Все эффективные (сокращающие полный
перебор) методы решения задачи коммивояжёра
— методы эвристические. В большинстве
эвристических методов находится не
самый эффективный маршрут, а приближённое
решение. Зачастую востребованы так
называемые any-time алгоритмы, то есть
постепенно улучшающие некоторое текущее
приближенное решение.

Задача коммивояжёра есть NP-полная
задача. Часто на ней проводят обкатку
новых подходов к эвристическому
сокращению полного перебора.

Класс задач NP
(от Nondeterminictic
Polinomial)
— это класс задач, для решения которых
полиномиального алгоритма может и не
существовать, но если решение нам
известно (например, мы его угадали), то
проверить его правильность за
полиномиальное время возможно
(полиномиальные алгоритмы проходят за
O(N^k)
число операций).

Внутри этого класса принято
выделять так называемые NP-полные
задачи. Полиномиальные алгоритмы решения
этих задач пока не найдены. Но все задачи
из этого класса можно свести друг к
другу. То есть, если окажется, что
какая-либо из NP-полных
задач решается за полиномиальное время,
то это будет означать, что и все остальные
задачи из этого класса эффективно
разрешимы.

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

Источник

Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.

Задача

Дан ориентированный граф (G = (V, E)), а также вершина (s).
Найти длину кратчайшего пути от (s) до каждой из вершин графа. Длина пути — количество рёбер в нём.

BFS

BFS — breadth-first search, или же поиск в ширину.

Этот алгоритм позволяет решать следующую задачу.

Алгоритм работает следующим образом.

Создадим массив (dist) расстояний. Изначально (dist[s] = 0) (поскольку расстояний от вершины до самой себя равно (0)) и (dist[v] = infty) для (v neq s).
Создадим очередь (q). Изначально в (q) добавим вершину (s).
Пока очередь (q) непуста, делаем следующее:
1. Извлекаем вершину (v) из очереди.
2. Рассматриваем все рёбра ((v, u) in E). Для каждого такого ребра пытаемся сделать релаксацию: если (dist[v] + 1 < dist[u]), то мы делаем присвоение (dist[u] = dist[v] + 1) и добавляем вершину (u) в очередь.

Визуализации:

https://visualgo.net/mn/dfsbfs
https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/

Интуитивное понимание алгоритма

Можно представить, что мы поджигаем вершину (s). Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.

Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину – ту непосещенную, которую мы положили в очередь раньше всего.

Оба алгоритма позволяют обойти граф целиком – посетить каждую вершину ровно один раз. Поэтому они оба подходят для таких задач как: * поиск компонент связности * проверка графа на двудольность * построение остова

Реализация на C++

n — количество вершин в графе; adj — список смежности

vector<int> bfs(int s) {
    // длина любого кратчайшего пути не превосходит n - 1,
    // поэтому n - достаточное значение для "бесконечности";
    // после работы алгоритма dist[v] = n, если v недостижима из s
    vector<int> dist(n, n);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return dist;
}

Свойства кратчайших путей

Обозначение: (d(v)) — длина кратчайшего пути от (s) до (v).

Лемма 1. > Пусть ((u, v) in E), тогда (d(v) leq d(u) + 1).

Действительно, существует путь из (s) в (u) длины (d(u)), а также есть ребро ((u, v)), следовательно, существует путь из (s) в (v) длины (d(u) + 1). А значит кратчайший путь из (s) в (v) имеет длину не более (d(u) + 1),

Лемма 2. > Рассмотрим кратчайший путь от (s) до (v). Обозначим его как (u_1, u_2, dots u_k) ((u_1 = s) и (u_k = v), а также (k = d(v) + 1)).
> Тогда (forall (i < k): d(u_i) + 1 = d(u_{i + 1})).

Действительно, пусть для какого-то (i < k) это не так. Тогда, используя лемму 1, имеем: (d(u_i) + 1 > d(u_{i + 1})). Тогда мы можем заменить первые (i + 1) вершин пути на вершины из кратчайшего пути из (s) в (u_{i + 1}). Полученный путь стал короче, но мы рассматривали кратчайший путь — противоречие.

Корректность

Утверждение. > 1. Расстояния до тех вершин, которые были добавлены в очередь, посчитаны корректно. > 2. Вершины лежат в очереди в порядке неубывания расстояния, притом разность между кратчайшими расстояними до вершин в очереди не превосходит (1).

Докажем это по индукции по количеству итераций алгоритма (итерация — извлечение вершины из очереди и дальнейшая релаксация).

База очевидна.
Переход. Сначала докажем первую часть. Предположим, что (dist[v] + 1 < dist[u]), но (dist[v] + 1) — некорректное расстояние до вершины (u), то есть (dist[v] + 1 neq d(u)). Тогда по лемме 1: (d(u) < dist[v] + 1). Рассмотрим предпоследнюю вершину (w) на кратчайшем пути от (s) до (u). Тогда по лемме 2: (d(w) + 1 = d(u)). Следовательно, (d(w) + 1 < dist[v] + 1) и (d(w) < dist[v]). Но тогда по предположению индукции (w) была извлечена раньше (v), следовательно, при релаксации из неё в очередь должна была быть добавлена вершина (u) с уже корректным расстоянием. Противоречие.
Теперь докажем вторую часть. По предположению индукции в очереди лежали некоторые вершины (u_1, u_2, dots u_k), для которых выполнялось следующее: (dist[u_1] leq dist[u_2] leq dots leq dist[u_k]) и (dist[u_k] – dist[u_1] leq 1). Мы извлекли вершину (v = u_1) и могли добавить в конец очереди какие-то вершины с расстоянием (dist[v] + 1). Если (k = 1), то утверждение очевидно. В противном случае имеем (dist[u_k] – dist[u_1] leq 1 leftrightarrow dist[u_k] – dist[v] leq 1 leftrightarrow dist[u_k] leq dist[v] + 1), то есть упорядоченность сохранилась. Осталось показать, что ((dist[v] + 1) – dist[u_2] leq 1), но это равносильно (dist[v] leq dist[u_2]), что, как мы знаем, верно.

Время работы

Из доказанного следует, что каждая достижимая из (s) вершина будет добавлена в очередь ровно (1) раз, недостижимые вершины добавлены не будут. Каждое ребро, соединяющее достижимые вершины, будет рассмотрено ровно (2) раза. Таким образом, алгоритм работает за (O(V+ E)) времени, при условии, что граф хранится в виде списка смежности.

Неориентированные графы

Если дан неориентированный граф, его можно рассматривать как ориентированный граф с двумя обратными друг другу ориентированными рёбрами.

Восстановление пути

Пусть теперь заданы 2 вершины (s) и (t), и необходимо не только найти длину кратчайшего пути из (s) в (t), но и восстановить какой-нибудь из кратчайших путей между ними. Всё ещё можно воспользоваться алгоритмом BFS, но необходимо ещё и поддерживать массив предков (p), в котором для каждой вершины будет храниться предыдущая вершина на кратчайшем пути.

Поддерживать этот массив просто: при релаксации нужно просто запоминать, из какой вершины мы прорелаксировали в данную. Также будем считать, что (p[s] = -1): у стартовой вершины предок — некоторая несуществующая вершина.

Восстановление пути делается с конца. Мы знаем последнюю вершину пути — это (t). Далее, мы сводим задачу к меньшей, переходя к нахождению пути из (s) в (p[t]).

Реализация BFS с восстановлением пути

// теперь bfs принимает 2 вершины, между которыми ищется пути
// bfs возвращает кратчайший путь из s в t, или же пустой vector, если пути нет
vector<int> bfs(int s, int t) {
    vector<int> dist(n, n);
    vector<int> p(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                p[u] = v;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    
    // если пути не существует, возвращаем пустой vector
    if (dist[t] == n) {
        return {};
    }

    vector<int> path;
    while (t != -1) {
        path.push_back(t);
        t = p[t];
    }
    
    // путь был рассмотрен в обратном порядке, поэтому его нужно перевернуть
    reverse(path.begin(), path.end());
    return path;
}

Проверка принадлежности вершины кратчайшему пути

Дан ориентированный граф (G), найти все вершины, которые принадлежат хотя бы одному кратчайшему пути из (s) в (t).

Запустим из вершины (s) в графе (G) BFS — найдём расстояния (d_1). Построим транспонированный граф (G^T) — граф, в котором каждое ребро заменено на противоположное. Запустим из вершины (t) в графе (G^T) BFS — найдём расстояния (d_2).

Теперь очевидно, что (v) принадлежит хотя бы одному кратчайшему пути из (s) в (t) тогда и только тогда, когда (d_1(v) + d_2(v) = d_1(t)) — это значит, что есть путь из (s) в (v) длины (d_1(v)), а затем есть путь из (v) в (t) длины (d_2(v)), и их суммарная длина совпадает с длиной кратчайшего пути из (s) в (t).

Кратчайший цикл в ориентированном графе

Найти цикл минимальной длины в ориентированном графе.

Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Это делается аналогично обычному BFS: мы должны найти расстояний от вершины до самой себя, при этом не считая, что оно равно (0).

Итого, у нас (|V|) запусков BFS, и каждый запуск работает за (O(|V| + |E|)). Тогда общее время работы составляет (O(|V|^2 + |V| |E|)). Если инициализировать массив (dist) единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за (O(|V||E|)).

Задача

Дан взвешенный ориентированный граф (G = (V, E)), а также вершина (s). Длина ребра ((u, v)) равна (w(u, v)). Длины всех рёбер неотрицательные.
Найти длину кратчайшего пути от (s) до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.

Алгоритм Дейкстры

Алгоритм Дейкстры решает приведённую выше задачу. Он работает следующим образом.

Создать массив (dist) расстояний. Изначально (dist[s] = 0) и (dist[v] = infty) для (v neq s).
Создать булёв массив (used), (used[v] = 0) для всех вершин (v) — в нём мы будем отмечать, совершалась ли релаксация из вершины.
Пока существует вершина (v) такая, что (used[v] = 0) и (dist[v] neq infty), притом, если таких вершин несколько, то (v) — вершина с минимальным (dist[v]), делать следующее:
1. Пометить, что мы совершали релаксацию из вершины (v), то есть присвоить (used[v] = 1).
2. Рассматриваем все рёбра ((v, u) in E). Для каждого ребра пытаемся сделать релаксацию: если (dist[v] + w(v, u) < dist[u]), присвоить (dist[u] = dist[v] + w(v, u)).

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

Посчитаем, за сколько работает алгоритм. Мы (V) раз ищем вершину минимальным (dist), поиск минимума у нас линейный за (O(V)), отсюда (O(V^2)). Обработка ребер у нас происходит суммарно за (O(E)), потому что на каждое ребро мы тратим (O(1)) действий. Так мы находим финальную асимптотику: (O(V^2 + E)).

Реализация на C++

Рёбра будем хранить как pair<int, int>, где первое число пары — куда оно ведёт; а второе — длина ребра.

// INF - infinity - бесконечность
const long long INF = (long long) 1e18 + 1;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n, INF);
    dist[s] = 0;
    vector<bool> used(n);
    
    while (true) {
        // находим вершину, из которой будем релаксировать
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                v = i;
            }
        }
        
        // если не нашли подходящую вершину, прекращаем работу алгоритма
        if (v == -1) {
            break;
        }
        
        for (auto &e : adj[v]) {
            int u = e.first;
            int len = e.second;
            if (dist[u] > dist[v] + len) {
                dist[u] = dist[v] + len;
            }
        }
    }
    
    return dist;
}

Восстановление пути

Восстановление пути в алгоритме Дейкстры делается аналогично восстановлению пути в BFS (и любой динамике).

Дейкстра на сете

Искать вершину с минимальным (dist) можно гораздо быстрее, используя такую структуру данных как очередь с приоритетом. Нам нужно хранить пары ((dist, index)) и уметь делать такие операции: * Извлечь минимум (чтобы обработать новую вершину) * Удалить вершину по индексу (чтобы уменьшить (dist) до какого-то соседа) * Добавить новую вершину (чтобы уменьшить (dist) до какого-то соседа)

Для этого используют, например, кучу или сет. Удобно помимо сета хранить сам массив dist, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение ((dist_1, u)) на ((dist_2, u)), нужно удалить из сета значение ((dist[u], u)), сделать (dist[u] = dist_2;) и добавить в сет ((dist[u], u)).

Данный алгоритм будет работать за (V O(log V)) извлечений минимума и (O(E log V)) операций уменьшения расстояния до вершины (может быть сделано после каждого ребра). Поэтому алгоритм работает за (O(E log V)).

Заметьте, что этот алгоритм не лучше и не хуже, чем без сета, который работает за (O(V^2 + E)). Ведь если (E = O(V^2)) (граф почти полный), то Дейкстра без сета работает быстрее, а если, наример, (E = O(V)), то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.

Источник

Определение[править | править код]

Задача о кратчайшем пути с учётом дополнительных ограничений[править | править код]

Алгоритмы[править | править код]

Задача поиска кратчайшего пути из одной вершины во все остальные[править | править код]

Невзвешенный ориентированный граф[править | править код]

Ориентированный граф с неотрицательными весами[править | править код]

Ориентированный граф с произвольными весами[править | править код]

Задача о кратчайшем пути между всеми парами вершин[править | править код]

Применение[править | править код]

Картографические сервисы[править | править код]

Недетерминированная машина[править | править код]

Сети дорог[править | править код]

Похожие задачи[править | править код]

Постановка задачи линейного программирования[править | править код]

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

Алгоритм Дейкстры. Разбор Задач

Введение

Примеры работы

Оценка сложности алгоритма

Задача №1

Решение

Задача №2

Решение

Заключение

Информация

Кто пользуется алгоритмом Дейкстры

Зачем нужен алгоритм Дейкстры

Как работает алгоритм

6.1. Нахождение кратчайшего пути

6.1.1. Прямой симметричный алгоритм

6.1.2. Задача коммивояжера

Задача

BFS

Интуитивное понимание алгоритма

Реализация на C++

Свойства кратчайших путей

Корректность

Время работы

Неориентированные графы

Восстановление пути

Реализация BFS с восстановлением пути

Проверка принадлежности вершины кратчайшему пути

Кратчайший цикл в ориентированном графе

Задача

Алгоритм Дейкстры

Реализация на C++

Восстановление пути

Дейкстра на сете

Вам также может понравиться

Как найти неизвестную операцию петерсон 2 класс

Как найти средний диаметр цилиндра

Нашел кольцо как избавиться

Добавить комментарий Отменить ответ