Просмотр кода страницы Задача о кратчайшем пути

[[Файл:Shortest path.svg|thumb|350px| Кратчайший путь (A, B, D, F) между вершинами A и F в неориентированном графе без весов.]]
[[Файл:Shortest path with direct weights.svg|thumb|350px|Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе.]]
'''Зада́ча о кратча́йшем пути́''' — задача поиска самого короткого [[Путь (теория графов)|пути]] (цепи) между двумя точками (вершинами) на [[Граф (математика)|графе]], в которой минимизируется сумма [[Взвешенный граф|весов рёбер]], составляющих путь.

Задача о кратчайшем пути является одной из важнейших классических задач [[теория графов|теории графов]]. Сегодня известно множество алгоритмов для её решения{{Переход|#Алгоритмы}}.

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

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

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

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

Пусть <math>e_{i, j}</math> — ребро соединяющее две вершины: <math>v_i</math> и <math>v_j</math>. Дана [[весовая функция]] <math>f: E \rightarrow \mathbb{R}</math>, которая отображает ребра на их веса, значения которых выражаются действительными числами, и неориентированный граф <math>G</math>. Тогда кратчайшим путём из вершины <math>v</math> в вершину <math>v'</math> будет называться путь <math>P = ( v_1, v_2, \ldots, v_n )</math> (где <math>v_1 = v</math> и <math>v_n = v'</math>), который имеет минимальное значение суммы <math>\sum_{i =1}^{n-1} f(e_{i, i+1}).</math> Если все ребра в графе имеют единичный вес, то задача сводится к определению наименьшего количества обходимых ребер.

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

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

== Задача о кратчайшем пути с учётом дополнительных ограничений ==
Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи{{sfn|Применение теории графов в программировании|1985}}. Примеры таких задач:
# Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теории [[Исследование операций|исследования операций]]{{sfn|Применение теории графов в программировании|1985|с=138—139}}.
# Минимальное [[Задача о вершинном покрытии|покрытие вершин]] ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути{{sfn|Применение теории графов в программировании|1985|с=139—142}}.
<!--# Метод минимального потока построения покрытия.
# Метод максимального [[Паросочетание|паросочетания]] для отыскания покрытия.-->
# Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей <math>P = {p_1, \dots, p_m}</math> такое, что для любого <math>t_i \in R</math> найдется путь <math>p_j \in P</math>, накрывающий его. <math>R = {t_1, \dots, t_k}</math> — множество некоторых путей в ориентированном графе G{{sfn|Применение теории графов в программировании|1985|с=144—145}}.
# Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмножества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины{{sfn|Применение теории графов в программировании|1985|с=145—148}}.

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

В работе (Черкасский и др., 1993){{sfn|Cherkassky, Goldberg, Radzik|1996}} представлено ещё несколько алгоритмов для решения этой задачи.

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

=== Невзвешенный ориентированный граф ===
{| class=wikitable
! Алгоритм !! Сложность !! Автор
|-
| [[Поиск в ширину]] || ''O''(''V+E'') ||
|}
{{expand list|date=December 2012}}

=== Ориентированный граф с неотрицательными весами ===
<!-- From Schrijver, Combinatorial Optimization, Volume A, p. 103 -->
{| class=wikitable
! Алгоритм !! Сложность !! Автор
|-
| - || ''O''(''V''<sup>2</sup>''EL'') || [[Форд, Лестер|Форд]] 1956
|-
| [[Алгоритм Беллмана — Форда]] || ''O''(''VE'') || [[Беллман, Ричард|Беллман]] 1958{{sfn|Bellman Richard|1958 }}, [[Мур, Эдвард Форест|Мур]] 1957{{sfn|Moore|1957}}
|-
| - || ''O''(''V''<sup>2</sup> log ''V'') || [[Данциг, Джордж|Данциг]] 1958, Данциг 1960, Minty (cf. Pollack&Wiebenson 1960), Whiting&Hillier 1960
|-
| [[Алгоритм Дейкстры]] со [[Список (информатика)|списком]]. || ''O''(''V''<sup>2</sup>) || Leyzorek et al. 1957{{sfn|M. Leyzorek|1957 }}, [[Дейкстра, Эдсгер Вибе|Дейкстра]] 1959{{sfn|Dijkstra|1959}}
|-
| Алгоритм Дейкстры с модифицированной [[Двоичная куча|двоичной кучей]] || ''O''((''E'' + ''V'') log ''V'') ||-
|-
| . . . || . . . || . . .
|- style="background: #90ff90"
| Алгоритм Дейкстры с использованием [[Фибоначчиева куча|фибоначчиевой кучи]] || ''O''(''E'' + ''V'' log ''V'') || Фридман&[[Тарьян, Роберт|Тарьян]] 1984{{sfn|Michael Fredman Lawrence|1984}}, Фридман&Тарьян 1987{{sfn|Fredman Michael|1987}}
|- style="background: #90ff90"
| - || ''O''(''E'' log log ''L'') || Джонсон 1982, Карлссон&Поблете 1983
|-
| [[Алгоритм Габова]] || ''O''(''E'' log<sub>''E''/''V''</sub> ''L'') || Габов 1983, Габов 1985
|- style="background: #90ff90"
| - || ''O''(''E'' + ''V''√log ''L'') || Ахуджа et al. 1990
|}
{{expand list|date=February 2011}}

=== Ориентированный граф с произвольными весами ===
{| class=wikitable
! Алгоритм !! Сложность !! Автор
|-
| [[Алгоритм Беллмана — Форда]] || ''O''(''VE'') || Беллман{{sfn|Bellman Richard|1958 }}, Мур{{sfn|Moore|1957}}
|-
| [[Алгоритм Левита]] || ''O''(''VE'') || 
|}
{{expand list|date=December 2012}}

== Задача о кратчайшем пути между всеми парами вершин ==
Задача о кратчайшем пути между всеми парами вершин для невзвешенного ориентированного графа была поставлена Симбелом в 1953 году{{sfn|Shimbel|1953}}, который обнаружил, что она может быть решена за линейное количество манипуляций (умножения) с матрицей. Сложность такого алгоритма ''O''(''V''<sup>4</sup>).

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

== Применение ==
Задача о поиске кратчайшего пути на графе может быть интерпретирована по-разному и применяться в различных областях. Далее приведены примеры различных применений задачи. Другие применения изучаются в дисциплине, которая занимается [[Исследование операций|исследованием операций]]{{sfn|Developing algorithms and software for geometric path planning problems|1996}}.

=== Картографические сервисы ===
Алгоритмы нахождения кратчайшего пути на графе применяются для нахождения путей между физическими объектами на таких картографических сервисах, как [[Google Maps|карты Google]] или [[OpenStreetMap]]. В обучающем видео от [[Google (компания)|Google]] можно узнать различные эффективные алгоритмы, которые применяются в данной сфере{{sfn|Fast route planning}}.

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

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

Сеть [[Дорога|дорог]] можно представить в виде графа с положительными весами. Вершины являются [[Транспортная развязка|дорожными развязками]], а ребра дорогами, которые их соединяют. Веса рёбер могут соответствовать протяжённости данного участка, времени необходимому для его преодоления или стоимости путешествия по нему. Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например автомагистрали). Она была формализована в понятии (идее) о магистралях{{sfn|Highway Dimension|2010}}.

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

Самый быстрый алгоритм может решить данную задачу на дорогах Европы или Америки за доли микросекунды{{sfn|A Hub-Based Labeling Algorithm|2011}}.

Другие подходы (техники), которые применяются в данной сфере:
* ALT
* Arc Flags
* [[:en:Contraction hierarchies|Contraction hierarchies]]
* Transit Node Routing
* Reach based Pruning
* Labeling

== Похожие задачи ==
Существуют задачи, которые похожи на задачу поиска кратчайшего пути на графе.

* Поиск кратчайшего пути в [[Вычислительная геометрия|вычислительной геометрии]] (см. [[:en:Euclidean shortest path|евклидов кратчайший путь]]).
* [[Задача коммивояжёра]]. Требуется найти кратчайший маршрут, проходящий через указанные города (вершины) хотя бы по одному разу с последующим возвратом в исходный город. Данная задача относится к классу NP-трудных задач в отличие от задачи поиска кратчайшего пути, которая может быть решена за полиномиальное время в графах без циклов. Задача коммивояжёра решается неэффективно для больших наборов данных.
* [[Задача канадского путешественника]] и задача стохастического поиска кратчайшего пути являются обобщением рассматриваемой задачи, в которых обходимый граф заранее полностью неизвестен и изменяется во времени или следующий проход по графу вычисляется на основе вероятностей.
* Задача поиска кратчайшего пути, когда в графе происходят преобразования. Например, изменяется вес ребра или удаляется вершина{{sfn|Ladyzhensky Y., Popoff Y. Algorithm|2006}}.

== Постановка задачи линейного программирования ==
Пусть дан направленный граф (''V'', ''A''), где ''V'' — множество вершин и ''A'' — множество рёбер, с начальной вершиной обхода ''s'', конечной ''t'' и весами ''w<sub>ij</sub>'' для каждого ребра (''i'', ''j'') в ''A''. Вес каждого ребра соответствует переменной программы ''x<sub>ij</sub>''.

Тогда задача ставится следующим образом: найти минимум функции <math>F=\sum_{ij \in A} w_{ij} x_{ij}</math>, где <math>x_{ij} \ge 0</math>, при условии что для всех ''i'' и ''j'' выполняется следующее неравенство: <math>\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}</math>

== См. также ==
* [[IEEE 802.1aq]]
* [[Транспортная сеть]]
* [[Двунаправленный поиск]]

== Примечания ==
{{примечания|22em}}

== Литература ==
* {{книга|автор={{nobr|Евстигнеев В. А.}}|часть=Глава 3. Итеративные алгоритмы глобального анализа графов. Пути и покрытия|заглавие=Применение теории графов в программировании|ссылка=web.archive.org/web/20131212234759/publ.lib.ru/ARCHIVES/E/EVSTIGNEEV_Vladimir_Anatol'evich/_Evstigneev_V.A..html|место=Москва|издательство=[[Наука (издательство)|Наука]]. Главная редакция физико-математической литературы|год=1985|страницы=138—150|страниц=352|ref=Применение теории графов в программировании|ответственный=Под ред. А. П. Ершова}}
* {{книга
 |автор        = {{nobr|Алексеев В.Е.,  Таланов В.А.}}
 |часть        = Глава 3.4. Нахождения кратчайших путей в графе
 |заглавие     = Графы. Модели вычислений. Структуры данных
 |ссылка       = http://f3.tiera.ru/ShiZ/Homelab/spec116/Alekseev%20V.E.,%20Talanov%20V.A.%20Grafy.%20Modeli%20vychislenij.%20Struktury%20dannyh.%20(2005).pdf
 |место        = Нижний Новгород
 |издательство = Издательство Нижегородского гос. университета
 |год          = 2005
 |страницы     = 236—237
 |страниц      = 307
 |ref          = Графы. Модели вычислений. Структуры данных
 |isbn         = 5–85747–810–8
}} {{Wayback|url=http://f3.tiera.ru/ShiZ/Homelab/spec116/Alekseev%20V.E.,%20Talanov%20V.A.%20Grafy.%20Modeli%20vychislenij.%20Struktury%20dannyh.%20(2005).pdf |date=20131213205803 }}
* {{книга
 |автор        = {{nobr|Галкина В.А}}
 |часть        = Глава 4. Построение кратчайших путей в ориентированном графе
 |заглавие     = Дискретная математика. Комбинаторная оптимизация на графах
 |место        = Москва
 |издательство = Издательство "Гелиос АРВ"
 |год          = 2003
 |страницы     = 75—94
 |страниц      = 232
 |ref          = Дискретная математика. Комбинаторная оптимизация на графах
 |isbn         = 5–85438–069–2
}}
* {{книга
 | автор          = {{nobr|Берж К.}}
 | часть          = Глава 7. Задача о кратчайшем пути
 | заглавие       = Теория графов и её применения
 | оригинал       = Theorie des graphes et ses applications
 | место          = Москва
 | издательство   = [[Издательство иностранной литературы]]
 | год            = 1962
 | страницы       = 75—81
 | страниц        = 320
 | ref            = Теория графов и её применения
 | ответственный  = Под ред. И. А. Вайнштейна
 | ответственный2 = Перев. А. А. Зыкова
}}
* {{книга|автор={{nobr|Ойстин Оре}}|заглавие=Теория графов|издательство=[[Наука (издательство)|Издательство наука]]|ссылка=http://share.auditory.ru/2011/Olga.Ionova/education/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5%20%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D1%8B%20%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F/PDF/Graph_theory_Ore.pdf|год=1980|страниц=336|ref=Теория графов, Оре|ответственный=Под ред. И. М. Овчинниковой}} {{Wayback|url=http://share.auditory.ru/2011/Olga.Ionova/education/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5%20%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D1%8B%20%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F/PDF/Graph_theory_Ore.pdf |date=20131215192042 }}
* Виталий Осипов, {{YouTube|BwB--ZvTNcE|Поиск кратчайших путей в дорожных сетях: от теории к реализации}}.
* {{source|Q28048620|part=Глава 2. Графы|pages=27|ref=Харари|ref-year=1973}} <!-- Теория графов -->
* {{source|Q28048899|ref=Cherkassky, Goldberg, Radzik|ref-year=1996}} <!-- Shortest paths algorithms: Theory and experimental evaluation // Math. Prog. -->
* {{статья
|заглавие=On a routing problem
|ссылка=https://archive.org/details/sim_quarterly-of-applied-mathematics_1958-04_16_1/page/87
|издание=Quarterly of Applied Mathematics
|том=16
|страницы=87—90
|mr=0102435
|ref=Bellman Richard
|автор=Ричард Беллман
|год=1958
}}
* {{source|Q21694527|ref=Dijkstra|ref-year=1959}} <!-- A note on two problems in connexion with graphs // Numer. Math -->
* {{source|Q28048674|ref=Moore|ref-year=1957}} <!-- The shortest path through a maze // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2-5 April 1957) -->
* {{книга |заглавие=Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems |издательство=Case Institute of Technology |место=Cleveland, Ohio |год=1957 |ref=M. Leyzorek |язык=en |автор=M. Leyzorek, R. S. Gray, A. A. Gray, W. C. Ladew, S. R. Meaker, R. M. Petry, R. N. Seitz}}
* {{статья |заглавие=Fibonacci heaps and their uses in improved network optimization algorithms |conference=25th Annual Symposium on Foundations of Computer Science |издательство=[[Институт инженеров электротехники и электроники]] |страницы=338—346 |ссылка=http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934 |ref=Michael Fredman Lawrence |doi=10.1109/SFCS.1984.715934 |isbn=0-8186-0591-X |язык=en |тип=journal |автор=Michael Fredman Lawrence, Роберт Андре Тарьян |год=1984 |издание= |archiveurl=https://web.archive.org/web/20121011090757/http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934 |archivedate=2012-10-11 }}
* {{статья |заглавие=Fibonacci heaps and their uses in improved network optimization algorithms |издание=[[Journal of the ACM|Journal of the Association for Computing Machinery]] |том=34 |номер=3 |страницы=596—615 |ссылка=http://portal.acm.org/citation.cfm?id=28874 |ref=Fredman Michael |doi=10.1145/28869.28874 |язык=en |тип=journal |автор=Michael Fredman Lawrence, Роберт Андре Тарьян |год=1987}}
* {{статья |заглавие=Structural parameters of communication networks |издание=Bulletin of Mathematical Biophysics |том=15 |номер=4 |страницы=501—507 |doi=10.1007/BF02476438 |ref=Shimbel |автор=Shimbel, Alfonso |год=1953 }}
* {{h|Fast route planning||{{статья |заглавие=Fast route planning |издательство=Google Tech Talk |ссылка=https://www.youtube.com/watch?v=-0ErpE8tQbw|автор=Sanders, Peter |число=23 |месяц=3 |год=2009 }}}}
* {{статья |doi=10.1145/242224.242246 |заглавие=Developing algorithms and software for geometric path planning problems |издание={{Нп3|ACM Computing Surveys}} |том=28 |номер=4es |страницы=18 |ref=Developing algorithms and software for geometric path planning problems |язык=en |тип=journal |автор=Chen, Danny Z. |месяц=12 |год=1996}}
* {{статья |ссылка=http://research.microsoft.com/pubs/115272/soda10.pdf%20research.microsoft.com/pubs/115272/soda10.pdf |заглавие=Highway Dimension, Shortest Paths, and Provably Efficient Algorithms |издание=ACM-SIAM Symposium on Discrete Algorithms |страницы=782—793 |ref=Highway Dimension |язык=en |тип=journal |автор=Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. |год=2010}}
* {{статья |ссылка=http://research.microsoft.com/pubs/142356/HL-TR.pdf |заглавие=A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks]. Symposium on Experimental Algorithms |страницы=230—241 |ref=A Hub-Based Labeling Algorithm |язык=en |тип=journal |автор=Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. |год=2011}}
* {{статья |doi=10.1016/j.cpc.2005.01.020 |заглавие=Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems |издание={{Нп3|Computer Physics Communications}} |том=168 |номер=168 |страницы=209—232 |ref=Shortest multiple disconnected path |язык=en |тип=journal |автор=Kroger, Martin |год=2005}}
* {{статья |заглавие=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 |страницы=68—75 |ref=Ladyzhensky Y., Popoff Y. Algorithm |язык=en |тип=journal |автор=Ladyzhensky Y., Popoff Y. |год=2006}}.{{нет АИ|6|11|2020}}

{{Внешние ссылки}}
{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы поиска на графах]]
[[Категория:Вычислительные задачи теории графов]]

{{спам-ссылки|1=
* https://web.archive.org/web/20131212234759/http://publ.lib.ru/ARCHIVES/E/EVSTIGNEEV_Vladimir_Anatol'evich/_Evstigneev_V.A..html
}}