Изменения

Дано{{Задача|definition = Дана сеть автомобильных дорог:* ориентированный граф <tex>G=(V,E)</tex>, где** <tex>V</tex> — множество перекрёстков,** <tex>E</tex> — множество дорог;* <tex>l(u,v) \geqslant 0</tex>— среднее время, которое занимает проезд по дороге,* <tex>|V|=n, |E|=m</tex>,* отправная точка - — вершина <tex>s</tex>, пункт назначения - — вершина <tex>t</tex> 

}}Мы будем рассматривать сеть автомобильных дорог:* <tex>V</tex> - множество Количество перекрёстков* <tex>E</tex> - множество и дорог* <tex>l(uможет быть очень большим,v)</tex> - среднее времятогда обычные алгоритмы поиска пути будут работать очень долго, которое занимает проезд по дорогепоэтому попытаемся оптимизировать их для более быстрой работы.

Основная статья: [[Алгоритм Дейкстры]]:* на На каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё,* завершает свою работу, когда цель достигнута (или просмотрены все вершины).

====Многоуровневые корзины (англ. ''multi-level buckets, MLB'')====

{| borderclass="1wikitable" cellspacingstyle="0width:7cm; text-align: center" cellpaddingborder="5" 1 align="right"

* Будем складывать вершины в "корзины" <tex>B[i] = \{u \in B[i] : distd(u)=i\}</tex>,* Наша наша структура данных будет поддерживать индекс <tex>L = \{\forall i : i<L \Rightarrow B[i] = \emptyset\}</tex>* На на каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>,* При при релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>distd(u)</tex> Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> - максимальная длина ребра в графе.

При двухуровневой Можно заметить, что при такой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать , все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализациивремя работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые где <tex>C</tex> — максимальная длина ребра в них входятграфе.

СоответственноПри двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят. В этом случае, нам нужно поддерживать два индекса <tex>L_{top}</tex> и <tex>L_{bottom}</tex> для каждого из уровней соответственно.

====Калибровка (англ. ''caliber'')====Введём величину <b><i>''калибр (caliber)</i>''</b> вершины <tex>c(v)</tex> - — вес минимального ребра, входящего в <tex>v</tex> , или <tex>\infty</tex>, если в вершину не входит ни одно ребро. Будем говорить, что текущее значение <tex>d(v)</tex> точно, если оно равно длине пути <tex>s \rightsquigarrow v</tex>.

Предположим, что длины рёбер неотрицательны. Пусть <tex>\mu</tex> - — минимальное из текущих значений <tex>d(v):v \in V</tex>. Тогда, если существует такая вершина <tex>u</tex>, что <tex>\mu + c(u) \geqslant d(u)</tex>, то текущее значение <tex>d(u)</tex> точно.

Модифицируем нашу MLB - — структуру: будем хранить помеченные вершины в двух группахструктурах: дерево поиска <tex>F</tex> и приоритетная очередь <tex>B</tex>, реализованная на MLB.Алгоритм, приведённый ниже, называется <b><i>''алгоритмом умной очереди ''</b> (англ. ''smart queue'')</i></b>.

Вершины в <tex>F</tex> будут иметь точные метки<tex>d(u)</tex>. Если <tex>F</tex> непусто, мы удалим оттуда вершину и прорелаксируем всех её соседей. Если же <tex>F</tex> пусто, мы достанем из

Рассмотрим механизм релаксации: пусть мы уменьшаем <tex>d(u)</tex>. Заметим, что в этом случае <tex>u</tex> не могло лежать в <tex>F</tex> (иначе <tex>d(u)</tex> было не точно). Если <tex>u \in B</tex> - — применим <tex>\mathtt{decrease - — key}</tex> к <tex>u</tex>. Эта операция либо переместила <tex>u</tex> внутри <tex>B</tex>, либо определила, что метка <tex>d(u)</tex> точна и переместила <tex>u</tex> в <tex>F</tex>.Если же <tex>u \notin F \hspace{2 mm} \& \hspace{2 mm} </tex> и <tex>u \notin B</tex>, мы применим операцию <tex>\mathtt{insert}</tex>, и <tex>u</tex> запишется в

Создадим две приоритетных очереди и запустим на одной из них алгоритм Дейкстры, ищущий <tex>d_{forward}(v)</tex> из <tex>s</tex>, а на другой - — ищущий <tex>d_{reverse}(v)</tex> из <tex>t</tex>. Алгоритм завершит свою работу, когда какая-нибудь вершина <tex>z</tex> будет удалена из обоих обеих очередей.

вершины с <tex>d_{reverse}(v)</tex> и найти ребро <tex>uv</tex> с минимальным <tex>d_{forward}(u)+\ell(uv)+ d_{reverse}(v) </tex>. Если эта величина меньше, чем длина первоначально найденного пути - — то это и есть результат работы алгоритма.

Основная статья: Приведём немного изменённую версию [[Алгоритм A*|этого алгоритма]] Приведём немного изменённую версию этого алгоритма.

Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> - — <b>''потенциал''<i/b>потенциал (aнгл. ''potential'')</i></b> вершины. Тогда, с её помощью можно определить <b>''потенциальную стоимость''<i/b>потенциальную стоимость (англ. ''reduced cost'')</i></b> каждого ребра как <tex>\ell_{h}(v,w) = \ell(v,w)-h(v)+h(w)</tex>

Назовём функцию <tex>h</tex> <b>правдоподобной (<i/b>(англ. ''feasible</i>'')</b>, если <tex>\forall (u,v): \ell_{h}(u,v) \geqslant 0</tex>. Известно, что, если <tex>h(t)\leqslant 0</tex> и <tex>h</tex> правдоподобна, то для любого <tex>v</tex>, <tex>h(v)</tex> - — нижняя граница <tex>distd(v,t)</tex>

Главное отличие от алгоритма Дейкстры в том, что A* является <b>информированным</b> алгоритмом - — он обрабатывает в первую очередь те вершины, которые находятся ближе к результату.

* в худшем случае - — <tex>h(v)=0</tex> - — вырождается в алгоритм Дейкстры* в лучшем случае - — <tex>\forall v: h(v)=distd(v,t)</tex>

* <tex>p_{f}(v)</tex>, оценивающая <tex>distd(v,t)</tex>* <tex>p_{r}(v)</tex>, оценивающая <tex>distd(s,v)</tex>

*<tex>\ell_{p_{f}}(v,w) = \ell(v,w)-p_{f}(v)+p_{f}(w)</tex> - — если ребро обрабатывается в обходе, начатом в <tex>s</tex>*<tex>\ell_{p_{r}}(v,w) = \ell(v,w)-p_{r}(w)+p_{r}(v)</tex> - — если ребро обрабатывается в обходе, начатом в <tex>t</tex>

Чтобы избежать этой проблемы, необходимо, чтобы <tex>\ell_{p_{f}}(v,w) = \ell_{p_{r}}(v,w) \Leftrightarrow p_{f}(v) + p_{r}(v) = p_{f}(w) + p_{r}(w) = const</tex>. Кроме того, функции должны бить быть монотонными.

Решение - — использовать усреднённые потенциальные функции:*<tex>h_{f}(v) = \fracdfrac{p_{f}(v)-p_{r}(v)}{2}</tex>*<tex>h_{r}(v) = \fracdfrac{p_{r}(v)-p_{f}(v)}{2} = -h_{f}(v)</tex>

# Препроцессинг:#* запускается единожды для графа,#* может занимать много времени,#* рассчитывает некую вспомогательную информацию.# Запрос:#* может использовать данные, полученные во время препроцессинга,#* запускается по требованию для пары <tex>(s,t)</tex>,#* должен выполняться очень быстро (в реальном времени).

* Алгоритм Дейкстры: препроцессинг - — ничего не делать, запрос - — выполнение алгоритма Дейкстры;* Полный перебор: препроцессинг - — посчитать таблицу расстояний размером <tex>n \times n</tex> (займёт порядка 5 лет времени и 1 петабайта памяти для карты Европы), запрос - — обратиться к элементу таблицы.

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

#Препроцессинг:#* взять небольшое количество вершин (например, 16), обозначив их как <b>ориентиры (landmarks)</b>(англ. ''landmarks''),#* для каждого из ориентиров посчитать кратчайшие пути до <b>всех</b> вершин,#* сохранить эти пути. #Запрос:#* используем A*,#* если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром - — по нему идём в первую очередь.

[[Файл:ALT.jpg|right|frame|рис. 1]]Будем использовать неравенство треугольника для нижних оценок пути(см. рис. 1). Пусть <tex>A</tex> — один из ориентиров, тогда:*<tex>dist(v,w)\ge geqslant dist(A,w)-dist(A,v)</tex>,*<tex>dist(v,w)\ge geqslant dist(v,A)-dist(w,A)</tex>,*<tex>dist(v,w)\ge geqslant \max\{dist(A,w)-dist(A,v),dist(v,A)-dist(w,A)\}</tex>.

* хороший ориентир для запроса <tex>s \rightsquigarrow t</tex> должен находиться "до" <tex>s</tex> (точно не будет общих рёбер на кратчайшем пути) или "за" <tex>t</tex> (чем острее угол, тем меньше отклонение от предварительно посчитанного кратчайшего пути до искомого),* Нам нам нужно выбрать такие ориентиры, которые будут неплохими для всех запросов.

* разделим Разделим карту на <tex>k</tex> секторов одинаковой площади,* возьмём ориентиром наиболее удалённую точку от центра в каждом секторе.

Оценим качество набора ориентиров <tex>S</tex> основываясь на покрытии дуг. Будем говорить, что ориентир <tex>L</tex> покрывает дугу <tex>(v,w)</tex>, если вершина <tex>v </tex> находится на кратчайшем пути <tex>L \rightsquigarrow w</tex>. То есть, <tex>\ell(v,w) = dist(L,w)-dist(L,v)</tex>, тогда такой выбор ориентира даст нам нижнюю границу для всех путей, содержащих <tex>(v,w)</tex>.

Пусть вершина <tex>v \in P</tex> лежит на кратчайшем пути <tex>P: s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом (reach)</b> (англ. ''reach'') вершины <tex>v</tex> относительно <tex>P</tex> величину <tex>r(v,P) = \min\{dist(s,v), dist(v,t)\}</tex>. Охватом вершины относительно всего графа назовём величину <tex>r(v) = \max\limits_{P} r(v,P)</tex> - — максимум по всем кратчайшим путям, содержащим <tex>v</tex>. Помимо этого, будет полезным ввести понятие охвата ребра. Назовём охватом ребра <tex>(v,w)\in P</tex> относительно <tex>P</tex> величину <tex>\min\{dist(s,v), dist(w,t)\}</tex>. Аналогично, охватом ребра относительно всего графа назовём величину <tex>r(v,w) = \max\limits_{P} r((v,w),P)</tex> — максимум по всем кратчайшим путям, содержащим <tex>(v,w)</tex>. 

* на больших автомагистралях вершины имеют большой охват,* на локальных перекрёстках (внутри населённых пунктов) вершины имеют маленький охват.

* удалим вершину <tex>w</tex>, если <tex>r(w)<\min\{d(s,v)+\ell(v,w), LB(w,t)\}</tex>,

* Явно: Евклидово расстояние, с помощью ориентиров.* Неявно: сделать поиск двунаправленным.

Таким образом, будем удалять <tex>w</tex>, если <tex>r(w)\textless \min\{d(s,v)+\ell(v,w), R_{t}\}</tex>

====Препроцессинг====Рассмотрим препроцессинг: 

* на начальном этапе <tex>\forall v \hspace{1px} : r(v)\leftarrow 0</tex>,* для каждой вершины <tex>s \in V</tex> рассмотрим дерево кратчайших путей до всех других вершин <tex>T_{s}</tex>. , **найдём наиболее длинный путь <tex>P_{s\rightsquigarrow t}</tex>, содержащий <tex>v</tex>. , **Назовём глубиной вершины <tex>d_{s}(v)</tex> расстояние от <tex>s</tex>, высотой вершины <tex>h_{s}(v)</tex> - — расстояние до наиболее далёкого потомка вершины,** Тогда, охватом вершины в этом дереве будет величина <tex>r_{s}(v) = \min\{d_{s}(v),h_{s}(v)\}</tex>,** Тогда обновим значение охвата <tex>r(v) \leftarrow \max\{r(v),r_{s}(v)\}</tex>. Сложность алгоритма: <tex>O(nm)</tex>, поэтому он слишком медленный для больших графов и его нужно улучшить.

Такой препроцессинг занимает порядка 12 часов даже на небольшом графеФинальная версия препроцессинга будет иметь две фазы:*основная фаза (~300K вершинстроятся частично обработанные деревья и добавляются сокращающие путь рёбра)*фаза отладки (вершины с большим охватом обрабатываются указанным выше алгоритмом — их гораздо меньше, поэтому его необходимо ускорить. обработка будет быстрой)

=====Сокращение области поиска=====Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon, \varepsilon=const</tex>. Заметим также, что если <tex>r(v) \geq geqslant \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq geqslant \varepsilon</tex>

Кратчайший Назовём кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> будет <tex>\varepsilon</tex>-минимальным тогда и только тогда, когда если выполняются условия:

*<tex>dist(s,v)\geqgeqslant\varepsilon</tex>; ,*<tex>dist(s',v)\textless\varepsilon</tex>; ,*<tex>dist(v,t)\geqgeqslant\varepsilon</tex>; ,*<tex>dist(v,t')\textless\varepsilon</tex>.

*найдём оценку охвата <tex>r'(v)</tex>, используя только <tex>\varepsilon</tex> - — минимальные пути,* если <tex>r'(v)<\varepsilon</tex>, то оценка корректна: <tex>r(v)=r'(v)</tex>,* если же <tex>r'(v)\geq geqslant \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geq geqslant r'(v)</tex>.

Полезно будет рассматривать <b>частично обработанные деревья</b> (<i>англ. ''partial trees</i>'') - — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:* Установим установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число),* Пока пока <tex>G'</tex> не пусто:** найдём частичное частично обработанное дерево кратчайших путейиз <tex>v</tex>, чтобы найти вершины с охватом <tex>r(v) \geq geqslant \varepsilon</tex>,** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>r(v) \textless\varepsilon</tex>, уже обработанные),** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>.

====Пенальти====Предыдущее улучшение создаёт проблему: мы должны предполагать, что кратчайший путь может начинаться в вершине с маленьким охватом, которые мы отбрасываем на каждой итерации. Для того, чтобы принять их во внимание, мы введём новую величину — <b>пенальти</b>(англ. ''penalty'') — верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне. Пусть <tex>G_{i} = (V_{i},E_A_{i})</tex> - — подграф исходного графа, полученный на <tex>i</tex>-й итерации алгоритма, описанного выше. Назовём входящим пенальти (<i>in-penalty</i>) вершины <tex>v\in V_{i}</tex> величину <tex>\max\{ \overline{r}(u,v) : u,v \in A \backslash A_{i}\}</tex>, если у <tex>v</tex> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.

* Глубиной вершины <tex>v\in T_{x}</tex>, где <tex>T_{x}</tex> - — частично обработанное дерево с корнем в <tex>x</tex> величину <tex>depth(v)=d(v)+in\textrm{--}penalty(x)</tex> , где <tex>d(v)</tex> - — длина пути от корня до вершины в дереве.* Чтобы определить высоту вершины, нам нужно понятие "ложных листьев". Для каждой вершины <tex>v</tex> в дереве кратчайших путей добавим потомка <tex>v'</tex> - — ложный лист, и ребро <tex>(v,v') = out\textrm{--}penalty(v)</tex>. В некотором смысле, <tex>v'</tex> будет выступать в роли всех рёбер, изначально инцидентных вершине <tex>v</tex>, которые мы отсекли. Тогда высотой вершины <tex>v</tex> будет расстояние от неё, до наиболее далёкого ложного листа. Подчеркнём, что в данный момент ложные листья добавляются неявно, и только после того, как дерево будет частично обработано. ====Сокращение путей====Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающее ребро</b> (англ. ''shortcut'') — ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа. На этом шаге мы будем искать <b>пропускаемые</b> (англ. ''bypassable'') вершины. Назовём вершину <tex>v</tex> пропускаемой, если выполняется одно из двух условий:* <tex>v</tex> имеет только одно входящее ребро <tex>(u,v)</tex> и одно исходящее ребро <tex>(v,w)</tex>,* <tex>v</tex> имеет два входящих ребра <tex>(u,v)</tex>, <tex>(w,v)</tex> и два исходящих ребра <tex>(v,w)</tex> ,<tex>(v,u)</tex>.В обоих случаях подразумевается, что <tex>u\neq w</tex>, то есть у <tex>v</tex> обязательно есть только два соседа. В первом случае, <tex>v</tex> — кандидат на односторонний пропуск (англ. ''one-way bypass''), во втором — на двухсторонний (англ. ''two-way bypass''). Мы будем использовать сокращающие рёбра, чтобы пропускать такие вершины. Линия (line) — путь в графе, содержащий как минимум три вершины, так, что все вершины, кроме начальной и конечной, пропускаемые. Каждая пропускаемая вершина может принадлежать только одной линии. Линии также могут быть односторонне- и двухсторонне- пропускаемыми, в зависимости от типа вершин, которые они содержат. Легко заметить, что на линии могут лежать вершины только одного типа. Как только мы нашли линию, самым простым решением будет добавить одно сокращающее ребро из начала в конец. Но практика показывает, что лучше сократить ещё и входящие в её состав линии меньшего размера, это ещё более уменьшит охваты пропускаемых вершин. Для этого перед добавлением сокращающего ребра по линии, рекурсивно найдём вершину, которая находится примерно на её середине и обработаем левый и правый отрезки как полноценные линии.====Удаление пропущенных вершин====Представим одностороннюю линию, состоящую из трёх вершин <tex>u</tex>, <tex>v</tex>, <tex>w</tex>. Когда мы добавили сокращающее ребро <tex>(u,w)</tex>, мы знали, что ребро <tex>(u,v)</tex> больше никогда не будет использоваться на кратчайшем пути содержащем подпуть <tex>u\rightsquigarrow w</tex>. Кроме того, любой кратчайший путь, содержащий <tex>(u,v)</tex>, будет оканчиваться либо в <tex>v</tex>, либо в близлежащей вершине с низким охватом.Тогда, корректной верхней оценкой охвата <tex>(u,v)</tex> является <tex>\overline{r}(u,v)=\ell(u,v)+out\textrm{-}penalty(v)</tex>. Аналогично, <tex>\overline{r}(v,w)=\ell(v,w)+in\textrm{-}penalty(v)</tex>. Зная это, мы можем удалить вершину <tex>v</tex> и смежные ей рёбра из графа и обновить соответствующие значения пенальти для её соседей. Такую же процедуру можно проделать с двусторонней линией, т.к. помимо оценок, указанных выше, можно добавить:* <tex>\overline{r}(w,v)=\ell(w,v)+out\textrm{-}penalty(v)</tex>,* <tex>\overline{r}(v,u)=\ell(v,u)+in\textrm{-}penalty(v)</tex>. ====Фаза отладки====Тот факт, что мы используем пенальти, для ускорения вычисления корректных верхних оценок охвата, приводит к тому, что оценки становятся менее точными в процессе работы алгоритма и с ростом пенальти. Следовательно, для вершин, которые дольше находятся в графе, ошибки накапливаются. Это плохо, потом что такие вершины и являются самыми важными в графе — у них высокий охват, их посещает большое количество кратчайших путей. Если бы мы могли сделать их более точными, во время запроса можно было бы пропустить большее количество вершин. В этом и заключается цель фазы отладки. После того, как мы найдём верные значения верхних оценок, используя частично обработанные деревья, во время фазы отладки мы пересчитаем охват <tex>\delta = const</tex> вершин с наибольшими значениями охвата (в них больше всего ошибок). Пусть <tex>V_{\delta} \subset G</tex> — множество вершин с высоким охватом мощностью <tex>\delta</tex>. Чтобы пересчитать их охваты, сначала необходимо найти подграф <tex>G_{\delta} = (V_{\delta},A_{\delta})</tex>. Этот граф содержит не только первоначальные рёбра, но и добавленные во время основной фазы сокращающие рёбра. Затем мы запустим поиск точных значений охвата для каждой вершины этого подграфа. Так как деревья кратчайших путей будут содержать только вершины из <tex>G_{\delta}</tex>, то нам всё ещё нужно использовать входящие и исходящие пенальти для остальных вершин. Но, тем не менее, они будут меньше, т.к. для самых больших мы подсчитали точное значение охвата. Во время фазы отладки мы заботимся о точности, а не о скорости, поэтому не добавляем новых сокращающих рёбер и используем точный алгоритм. Поэтому, время работы алгоритма как минимум <tex>\Omega(\delta^{2})</tex> ==Итог=={| class="wikitable" style="width:17cm; text-align: center" border=1 |+ Сравнение различных эвристик для поиска кратчайшего пути на карте США ! Метод !! Время препроцессинга, м !! Память для препроцессинга, MB !! Сканируемые запросом вершины, шт !! Время запроса, мс |- | Алгоритм Дейкстры || - || 536 || 11 808 864 || 5440,5 |- | ALT(16 ориентиров) || 18 || 2563 || 187 968 || 295,45 |- | Reach || 28 || 893 || 2 405 || 1,77 |- |}  {| border="0" cellspacing="0" cellpadding="5" |+ Работа различных алгоритмов на карте севера США ! Алгоритм Дейкстры !!ALT (16 ориентиров) !! Reach |- | [[Файл:Ex1.jpg]] || [[Файл:Ex2.jpg]] || [[Файл:Ex3.jpg]] |- |}Условные обозначения:* зелёный квадрат — начало пути* синий квадрат — конец пути* зелёные линии — пути, пройденные прямым обходом* синие линии — пути, пройденные обратным обходом* красные ромбы — ориентиры* жёлтые ромбы — выбранные при поиске пути ориентиры

==См. также===Сокращение путей=====Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающий путь</b> (<i>shortcut</i>) - ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.*[[Алгоритм Дейкстры]]*[[Алгоритм A*]]

==СсылкиИсточники информации==*[http://logic.pdmi.ras.ru/midas/sites/default/files/midas-werneck.pdf Презентация Renato Werneck c MIDAS 2010 - основа конспекта]