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

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 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..^{[источник не указан 924 дня]}

Источник

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

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

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

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.

Алгоритм Флойда-Уоршелла

Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
n итераций по n итераций по n итераций, итого порядка n^3 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
d = g
for i = 1 ... n + 1
     for j = 0 ... n - 1
          for k = 0 ... n - 1
              if d[j][k] > d[j][i - 1] + d[i - 1][k]
                  d[j][k] = d[j][i - 1] + d[i - 1][k]
вывести d

Алгоритм Форда-Беллмана

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
n итераций по m итераций, итого порядка n * m операций.
Псевдокод:

прочитать e // e[0 ... m - 1] - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра)
for i = 0 ... n - 1
    d[i] = 2000000000
d[0] = 0
for i = 1 ... n
    for j = 0 ... m - 1
        if d[e[j].second] > d[e[j].first] + e[j].value
            d[e[j].second] = d[e[j].first] + e[j].value
        if d[e[j].first] > d[e[j].second] + e[j].value
            d[e[j].first] = d[e[j].second] + e[j].value
вывести d

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

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны.
На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
d = g
d[0] = 0
mark[0] = True
for i = 1 ... n - 1
    mark[i] = False
for i = 1 ... n - 1
    v = -1
    for i = 0 ... n - 1
        if (not mark[i]) and ((v == -1) or (d[v] > d[i]))
            v = i
    mark[v] = True
    for i = 0 ... n - 1
        if d[i] > d[v] + g[v][i]
            d[i] = d[v] + g[v][i]
вывести d

Алгоритм Дейкстры для разреженных графов

Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m * log(n). Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.
Псевдокод:

прочитать g // g[0 ... n - 1] - массив списков, в i-ом списке хранятся пары: first - вершина, соединённая с i-ой вершиной ребром, second - вес этого ребра
d[0] = 0
for i = 0 ... n - 1
    d[i] = 2000000000
for i in g[0] // python style
    d[i.first] = i.second
    q.add(pair(i.second, i.first))
for i = 1 ... n - 1
    v = -1
    while (v = -1) or (d[v] != val)
        v = q.top.second
        val = q.top.first
    q.removeTop
    mark[v] = true
    for i in g[v]
        if d[i.first] > d[v] + i.second
            d[i.first] = d[v] + i.second
            q.add(pair(d[i.first], i.first))
вывести d

Источник

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

Задача

Дан ориентированный граф (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)), то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.

Источник

From Wikipedia, the free encyclopedia

Shortest path (A, C, E, D, F) between vertices A and F in the weighted directed graph

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.

Definition[edit]

The shortest path problem can be defined for graphs whether undirected, directed, or mixed.
It is defined here for undirected graphs; for directed graphs the definition of path
requires that consecutive vertices be connected by an appropriate directed edge.

Two vertices are adjacent when they are both incident to a common edge.
A path in an undirected graph is a sequence of vertices ${displaystyle P=(v_{1},v_{2},ldots ,v_{n})in Vtimes Vtimes cdots times V}$
such that $v_{i}$ is adjacent to $v_{i+1}$ for .
Such a path is called a path of length n-1
from $v_{1}$ to $v_{n}$ .
(The $v_{i}$ are variables; their numbering here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)

Let $e_{i,j}$ be the edge incident to both $v_{i}$ and $v_{j}$ . Given a real-valued weight function , and an undirected (simple) graph , the shortest path from to is the path $P=(v_{1},v_{2},ldots ,v_{n})$ (where $v_{1}=v$ and $v_{n}=v'$ ) that over all possible minimizes the sum $sum _{i=1}^{n-1}f(e_{i,i+1}).$ When each edge in the graph has unit weight or , this is equivalent to finding the path with fewest edges.

The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations:

The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph.
The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices v, v’ in the graph.

These generalizations have significantly more efficient algorithms than the simplistic approach of running a single-pair shortest path algorithm on all relevant pairs of vertices.

Algorithms[edit]

The most important algorithms for solving this problem are:

Dijkstra’s algorithm solves the single-source shortest path problem with non-negative edge weight.
Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
A* search algorithm solves for single-pair shortest path using heuristics to try to speed up the search.
Floyd–Warshall algorithm solves all pairs shortest paths.
Johnson’s algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.

Additional algorithms and associated evaluations may be found in Cherkassky, Goldberg & Radzik (1996).

Single-source shortest paths[edit]

Undirected graphs[edit]

Weights	Time complexity	Author
₊	O(V²)	Dijkstra 1959
₊	O((E + V) log V)	Johnson 1977 (binary heap)
₊	O(E + V log V)	Fredman & Tarjan 1984 (Fibonacci heap)
	O(E)	Thorup 1999 (requires constant-time multiplication)

Unweighted graphs[edit]

Algorithm	Time complexity	Author
Breadth-first search	O(E + V)

Directed acyclic graphs (DAGs)[edit]

An algorithm using topological sorting can solve the single-source shortest path problem in time Θ(E + V) in arbitrarily-weighted DAGs.^[1]

Directed graphs with nonnegative weights[edit]

The following table is taken from Schrijver (2004), with some corrections and additions.
A green background indicates an asymptotically best bound in the table; L is the maximum length (or weight) among all edges, assuming integer edge weights.

Algorithm	Time complexity	Author
		Ford 1956
Bellman–Ford algorithm		Shimbel 1955, Bellman 1958, Moore 1959
	${displaystyle O(V^{2}log {V})}$	Dantzig 1960
Dijkstra’s algorithm with list		Leyzorek et al. 1957, Dijkstra 1959, Minty (see Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dijkstra’s algorithm with binary heap		Johnson 1977
Dijkstra’s algorithm with Fibonacci heap		Fredman & Tarjan 1984, Fredman & Tarjan 1987
Dial’s algorithm^[2] (Dijkstra’s algorithm using a bucket queue with L buckets)		Dial 1969
		Johnson 1981, Karlsson & Poblete 1983
Gabow’s algorithm	${displaystyle O(Elog _{E/V}L)}$	Gabow 1983, Gabow 1985
		Ahuja et al. 1990
Thorup		Thorup 2004

Directed graphs with arbitrary weights without negative cycles[edit]

Algorithm	Time complexity	Author
	O(V²EL)	Ford 1956
Bellman–Ford algorithm	O(VE)	Shimbel 1955, Bellman 1958, Moore 1959
Johnson-Dijkstra with binary heap	O(V (E + log V))	Johnson 1977
Johnson-Dijkstra with Fibonacci heap	O(V (E + log V))	Fredman & Tarjan 1984, Fredman & Tarjan 1987, adapted after Johnson 1977
Johnson’s technique applied to Dial’s algorithm^[2]	O(V (E + L))	Dial 1969, adapted after Johnson 1977

Directed graphs with arbitrary weights with negative cycles[edit]

Finds a negative cycle or calculates distances to all vertices.

Weights	Algorithm	Time complexity	Author
	Andrew V. Goldberg

Planar graphs with nonnegative weights[edit]

Weights	Algorithm	Time complexity	Author
${displaystyle mathbb {R} _{geq 0}}$			Henzinger et al. 1997

All-pairs shortest paths[edit]

The all-pairs shortest path problem finds the shortest paths between every pair of vertices v, v’ in the graph. The all-pairs shortest paths problem for unweighted directed graphs was introduced by Shimbel (1953), who observed that it could be solved by a linear number of matrix multiplications that takes a total time of O(V⁴).

Undirected graph[edit]

Weights	Time complexity	Algorithm
₊	O(V³)	Floyd–Warshall algorithm
	${displaystyle O(V^{omega }log V)}$	Seidel’s algorithm (expected running time)
	$O(V^{3}/2^{Omega (log n)^{1/2}})$	Williams 2014
₊	O(EV log α(E,V))	Pettie & Ramachandran 2002
	O(EV)	Thorup 1999 applied to every vertex (requires constant-time multiplication).

Directed graph[edit]

Weights	Time complexity	Algorithm
(no negative cycles)	O(V³)	Floyd–Warshall algorithm
	$O(V^{3}/2^{Omega (log n)^{1/2}})$	Williams 2014
(no negative cycles)	O(EV + V² log V)	Johnson–Dijkstra
(no negative cycles)	O(EV + V² log log V)	Pettie 2004
	O(EV + V² log log V)	Hagerup 2000

Applications[edit]

Shortest path algorithms are applied to automatically find directions between physical locations, such as driving directions on web mapping websites like MapQuest or Google Maps. For this application fast specialized algorithms are available.^[3]

If one represents a nondeterministic abstract machine as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state. For example, if vertices represent the states of a puzzle like a Rubik’s Cube and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.

In a networking or telecommunications mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a widest path problem. For example, the algorithm may seek the shortest (min-delay) widest path, or widest shortest (min-delay) path.

A more lighthearted application is the games of “six degrees of separation” that try to find the shortest path in graphs like movie stars appearing in the same film.

Other applications, often studied in operations research, include plant and facility layout, robotics, transportation, and VLSI design.^[4]

Road networks[edit]

A road network can be considered as a graph with positive weights. The nodes represent road junctions and each edge of the graph is associated with a road segment between two junctions. The weight of an edge may correspond to the length of the associated road segment, the time needed to traverse the segment, or the cost of traversing the segment. Using directed edges it is also possible to model one-way streets. Such graphs are special in the sense that some edges are more important than others for long-distance travel (e.g. highways). This property has been formalized using the notion of highway dimension.^[5] There are a great number of algorithms that exploit this property and are therefore able to compute the shortest path a lot quicker than would be possible on general graphs.

All of these algorithms work in two phases. In the first phase, the graph is preprocessed without knowing the source or target node. The second phase is the query phase. In this phase, source and target node are known. The idea is that the road network is static, so the preprocessing phase can be done once and used for a large number of queries on the same road network.

The algorithm with the fastest known query time is called hub labeling and is able to compute shortest path on the road networks of Europe or the US in a fraction of a microsecond.^[6] Other techniques that have been used are:

ALT (A* search, landmarks, and triangle inequality)
Arc flags
Contraction hierarchies
Transit node routing
Reach-based pruning
Labeling
Hub labels

[edit]

For shortest path problems in computational geometry, see Euclidean shortest path.

The shortest multiple disconnected path ^[7] is a representation of the primitive path network within the framework of Reptation theory. The widest path problem seeks a path so that the minimum label of any edge is as large as possible.

Other related problems may be classified into the following categories.

Paths with constraints[edit]

Unlike the shortest path problem, which can be solved in polynomial time in graphs without negative cycles, shortest path problems which include additional constraints on the desired solution path are called Constrained Shortest Path First, and are harder to solve. One example is the constrained shortest path problem,^[8] which attempts to minimize the total cost of the path while at the same time maintaining another metric below a given threshold. This makes the problem NP-complete (such problems are not believed to be efficiently solvable for large sets of data, see P = NP problem). Another NP-complete example requires a specific set of vertices to be included in the path,^[9] which makes the problem similar to the Traveling Salesman Problem (TSP). The TSP is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. The problem of finding the longest path in a graph is also NP-complete.

Partial observability[edit]

The Canadian traveller problem and the stochastic shortest path problem are generalizations where either the graph isn’t completely known to the mover, changes over time, or where actions (traversals) are probabilistic. ^[10] ^[11]

Strategic shortest paths[edit]

Sometimes, the edges in a graph have personalities: each edge has its own selfish interest. An example is a communication network, in which each edge is a computer that possibly belongs to a different person. Different computers have different transmission speeds, so every edge in the network has a numeric weight equal to the number of milliseconds it takes to transmit a message. Our goal is to send a message between two points in the network in the shortest time possible. If we know the transmission-time of each computer (the weight of each edge), then we can use a standard shortest-paths algorithm. If we do not know the transmission times, then we have to ask each computer to tell us its transmission-time. But, the computers may be selfish: a computer might tell us that its transmission time is very long, so that we will not bother it with our messages. A possible solution to this problem is to use a variant of the VCG mechanism, which gives the computers an incentive to reveal their true weights.

Negative cycle detection[edit]

In some cases, the main goal is not to find the shortest path, but only to detect if the graph contains a negative cycle. Some shortest-paths algorithms can be used for this purpose:

The Bellman–Ford algorithm can be used to detect a negative cycle in time .
Cherkassky and Goldberg^[12] survey several other algorithms for negative cycle detection.

General algebraic framework on semirings: the algebraic path problem[edit]

This section needs expansion. You can help by adding to it. (August 2014)

Many problems can be framed as a form of the shortest path for some suitably substituted notions of addition along a path and taking the minimum. The general approach to these is to consider the two operations to be those of a semiring. Semiring multiplication is done along the path, and the addition is between paths. This general framework is known as the algebraic path problem.^[13]^[14]^[15]

Most of the classic shortest-path algorithms (and new ones) can be formulated as solving linear systems over such algebraic structures.^[16]

More recently, an even more general framework for solving these (and much less obviously related problems) has been developed under the banner of valuation algebras.^[17]

Shortest path in stochastic time-dependent networks[edit]

In real-life situations, the transportation network is usually stochastic and time-dependent. In fact, a traveler traversing a link daily may experiences different travel times on that link due not only to the fluctuations in travel demand (origin-destination matrix) but also due to such incidents as work zones, bad weather conditions, accidents and vehicle breakdowns. As a result, a stochastic time-dependent (STD) network is a more realistic representation of an actual road network compared with the deterministic one.^[18]^[19]

Despite considerable progress during the course of the past decade, it remains a controversial question how an optimal path should be defined and identified in stochastic road networks. In other words, there is no unique definition of an optimal path under uncertainty. One possible and common answer to this question is to find a path with the minimum expected travel time. The main advantage of using this approach is that efficient shortest path algorithms introduced for the deterministic networks can be readily employed to identify the path with the minimum expected travel time in a stochastic network. However, the resulting optimal path identified by this approach may not be reliable, because this approach fails to address travel time variability. To tackle this issue some researchers use distribution of travel time instead of expected value of it so they find the probability distribution of total travelling time using different optimization methods such as dynamic programming and Dijkstra’s algorithm .^[20] These methods use stochastic optimization, specifically stochastic dynamic programming to find the shortest path in networks with probabilistic arc length.^[21] The concept of travel time reliability is used interchangeably with travel time variability in the transportation research literature, so that, in general, one can say that the higher the variability in travel time, the lower the reliability would be, and vice versa.

In order to account for travel time reliability more accurately, two common alternative definitions for an optimal path under uncertainty have been suggested. Some have introduced the concept of the most reliable path, aiming to maximize the probability of arriving on time or earlier than a given travel time budget. Others, alternatively, have put forward the concept of an α-reliable path based on which they intended to minimize the travel time budget required to ensure a pre-specified on-time arrival probability.

References[edit]

Notes[edit]

^ Cormen et al. 2001, p. 655
^ ^a ^b Dial, Robert B. (1969). “Algorithm 360: Shortest-Path Forest with Topological Ordering [H]”. Communications of the ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
^ Sanders, Peter (March 23, 2009). “Fast route planning”. Google Tech Talk. Archived from the original on 2021-12-11.
^ Chen, Danny Z. (December 1996). “Developing algorithms and software for geometric path planning problems”. ACM Computing Surveys. 28 (4es). Article 18. doi:10.1145/242224.242246. S2CID 11761485.
^ Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. “Highway Dimension, Shortest Paths, and Provably Efficient Algorithms”. ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.
^ Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf “A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks”. Symposium on Experimental Algorithms, pages 230–241, 2011.
^ Kroger, Martin (2005). “Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems”. Computer Physics Communications. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016/j.cpc.2005.01.020.
^ Lozano, Leonardo; Medaglia, Andrés L (2013). “On an exact method for the constrained shortest path problem”. Computers & Operations Research. 40 (1): 378–384. doi:10.1016/j.cor.2012.07.008.
^ Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). “Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search”. 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS): 3519–3525. arXiv:2108.01036. doi:10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID 210706773.
^ Bar-Noy, Amotz; Schieber, Baruch (1991). “The canadian traveller problem”. Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms: 261–270. CiteSeerX 10.1.1.1088.3015.
^ Nikolova, Evdokia; Karger, David R. “Route planning under uncertainty: the Canadian traveller problem” (PDF). Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI): 969–974. Archived (PDF) from the original on 2022-10-09.
^ Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). “Negative-cycle detection algorithms”. Mathematical Programming. 85 (2): 277–311. doi:10.1007/s101070050058. ISSN 1436-4646. S2CID 79739.
^ Pair, Claude (1967). “Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)”. In Rosentiehl, Pierre (ed.). Théorie des graphes (journées internationales d’études) — Theory of Graphs (international symposium). Rome (Italy), July 1966: Dunod (Paris) et Gordon and Breach (New York). p. 271.{{cite conference}}: CS1 maint: location (link)
^ Derniame, Jean Claude; Pair, Claude (1971). Problèmes de cheminement dans les graphes (Path Problems in Graphs). Dunod (Paris).
^ Baras, John; Theodorakopoulos, George (4 April 2010). Path Problems in Networks. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3.
^ Gondran, Michel; Minoux, Michel (2008). Graphs, Dioids and Semirings: New Models and Algorithms. Springer Science & Business Media. chapter 4. ISBN 978-0-387-75450-5.
^ Pouly, Marc; Kohlas, Jürg (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. Chapter 6. Valuation Algebras for Path Problems. ISBN 978-1-118-01086-0.
^ Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.
^ Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). “Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm”. Expert Systems with Applications. 42 (12): 5056–5064. doi:10.1016/j.eswa.2015.02.046.
^ Olya, Mohammad Hessam (2014). “Finding shortest path in a combined exponential – gamma probability distribution arc length”. International Journal of Operational Research. 21 (1): 25–37. doi:10.1504/IJOR.2014.064020.
^ Olya, Mohammad Hessam (2014). “Applying Dijkstra’s algorithm for general shortest path problem with normal probability distribution arc length”. International Journal of Operational Research. 21 (2): 143–154. doi:10.1504/IJOR.2014.064541.

Bibliography[edit]

Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (April 1990). “Faster algorithms for the shortest path problem” (PDF). Journal of the ACM. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589. Archived (PDF) from the original on 2022-10-09.
Bellman, Richard (1958). “On a routing problem”. Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090/qam/102435. MR 0102435.
Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). “Shortest paths algorithms: theory and experimental evaluation”. Mathematical Programming. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. MR 1392160.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. “Single-Source Shortest Paths and All-Pairs Shortest Paths”. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 580–642. ISBN 0-262-03293-7.
Dantzig, G. B. (January 1960). “On the Shortest Route through a Network”. Management Science. 6 (2): 187–190. doi:10.1287/mnsc.6.2.187.
Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs”. Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID 123284777.
Ford, L. R. (1956). “Network Flow Theory”. Rand Corporation. P-923.
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). “Fibonacci heaps and their uses in improved network optimization algorithms”. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
Gabow, H. N. (1983). “Scaling algorithms for network problems”. Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983) (PDF). pp. 248–258. doi:10.1109/SFCS.1983.68.
Gabow, Harold N. (1985). “Scaling algorithms for network problems”. Journal of Computer and System Sciences. 31 (2): 148–168. doi:10.1016/0022-0000(85)90039-X. MR 0828519.
Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P.; Welzl, Emo (eds.). Improved Shortest Paths on the Word RAM. Proceedings of the 27th International Colloquium on Automata, Languages and Programming. pp. 61–72. ISBN 978-3-540-67715-4.
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997). “Faster Shortest-Path Algorithms for Planar Graphs”. Journal of Computer and System Sciences. 55 (1): 3–23. doi:10.1006/jcss.1997.1493.
Johnson, Donald B. (1977). “Efficient algorithms for shortest paths in sparse networks”. Journal of the ACM. 24 (1): 1–13. doi:10.1145/321992.321993. S2CID 207678246.
Altıntaş, Gökhan (2020). Exact Solutions of Shortest-Path Problems Based on Mechanical Analogies: In Connection with Labyrinths. Amazon Digital Services LLC. p. 97. ISBN 9798655831896.
Johnson, Donald B. (December 1981). “A priority queue in which initialization and queue operations take O(log log D) time”. Mathematical Systems Theory. 15 (1): 295–309. doi:10.1007/BF01786986. MR 0683047. S2CID 35703411.
Karlsson, Rolf G.; Poblete, Patricio V. (1983). “An O(m log log D) algorithm for shortest paths”. Discrete Applied Mathematics. 6 (1): 91–93. doi:10.1016/0166-218X(83)90104-X. MR 0700028.
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. (1957). 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.
Moore, E. F. (1959). “The shortest path through a maze”. Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press. pp. 285–292.
Pettie, Seth; Ramachandran, Vijaya (2002). Computing shortest paths with comparisons and additions. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 267–276. ISBN 978-0-89871-513-2.
Pettie, Seth (26 January 2004). “A new approach to all-pairs shortest paths on real-weighted graphs”. Theoretical Computer Science. 312 (1): 47–74. doi:10.1016/s0304-3975(03)00402-x.
Pollack, Maurice; Wiebenson, Walter (March–April 1960). “Solution of the Shortest-Route Problem—A Review”. Oper. Res. 8 (2): 224–230. doi:10.1287/opre.8.2.224. Attributes Dijkstra’s algorithm to Minty (“private communication”) on p. 225.
Schrijver, Alexander (2004). Combinatorial Optimization — Polyhedra and Efficiency. Algorithms and Combinatorics. Vol. 24. Springer. ISBN 978-3-540-20456-5. Here: vol.A, sect.7.5b, p. 103
Shimbel, Alfonso (1953). “Structural parameters of communication networks”. Bulletin of Mathematical Biophysics. 15 (4): 501–507. doi:10.1007/BF02476438.
Shimbel, A. (1955). Structure in communication nets. Proceedings of the Symposium on Information Networks. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
Thorup, Mikkel (1999). “Undirected single-source shortest paths with positive integer weights in linear time”. Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
Thorup, Mikkel (2004). “Integer priority queues with decrease key in constant time and the single source shortest paths problem”. Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003.
Whiting, P. D.; Hillier, J. A. (March–June 1960). “A Method for Finding the Shortest Route through a Road Network”. Operational Research Quarterly. 11 (1/2): 37–40. doi:10.1057/jors.1960.32.
Williams, Ryan (2014). “Faster all-pairs shortest paths via circuit complexity”. Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC ’14). New York: ACM. pp. 664–673. arXiv:1312.6680. doi:10.1145/2591796.2591811. MR 3238994.

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Флойда-Уоршелла

Алгоритм Форда-Беллмана

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

Алгоритм Дейкстры для разреженных графов

Задача

BFS

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

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

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

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

Время работы

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

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

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

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

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

Задача

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

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

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

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

Definition[edit]

Algorithms[edit]

Single-source shortest paths[edit]

Undirected graphs[edit]

Unweighted graphs[edit]

Directed acyclic graphs (DAGs)[edit]

Directed graphs with nonnegative weights[edit]

Directed graphs with arbitrary weights without negative cycles[edit]

Directed graphs with arbitrary weights with negative cycles[edit]

Planar graphs with nonnegative weights[edit]

All-pairs shortest paths[edit]

Undirected graph[edit]

Directed graph[edit]

Applications[edit]

Road networks[edit]

[edit]

Paths with constraints[edit]

Partial observability[edit]

Strategic shortest paths[edit]

Negative cycle detection[edit]

General algebraic framework on semirings: the algebraic path problem[edit]

Shortest path in stochastic time-dependent networks[edit]

See also[edit]

References[edit]

Notes[edit]

Bibliography[edit]

Further reading[edit]

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

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

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

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

Как найти крайние точки на физической карте

Как фотошопом исправить смазана фото

Как найти активное сопротивление катушки индуктивности

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