262
правки
Изменения
м
Нет описания правки
Предположим, что длины рёбер неотрицательны. Пусть <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> точно.
}}
Эта лемма позволяет нам смягчить правило выбора текущей вершины в алгоритме Дейкстры, при этом сохраняя инвариант(почти все вершины обрабатываются единожды).
Калибровка использует Лемму 1 чтобы находить и обрабатывать вершины с точными текущими значениями расстояния до них.
<tex>B</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} u \notin B</tex>, мы применим операцию <tex>\mathtt{insert}</tex>, и <tex>u</tex> запишется в
<tex>F</tex> или <tex>B</tex>, в зависимости от того, выполняется ли условие леммы.
=====Сокращение путей=====
Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающий путь</b> (<i>shortcut</i>) - ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг(уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.
==Ссылки==
