Изменения

Введём величину "<b><i>калибр" </i></b> вершины <tex>c(v)</tex>- вес минимального ребра, входящего в <tex>v</tex>, или <tex>\infty</tex>, если в вершину не входит ни одно ребро. Будем говорить, что текущее значение <tex>d(v)</tex> точно, если оно равно длине пути <tex>s \rightsquigarrow v</tex>. {{Лемма|about = 1|statement = Предположим, что длины рёбер неотрицательны. Пусть <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 чтобы находить и обрабатывать вершины с точными текущими значениями расстояния до них. Модифицируем нашу MLB - структуру: будем хранить помеченные вершины в двух группах: сет <tex>F</tex> и приоритетная очередь <tex>B</tex>, реализованная на MLB.Назовём наш алгоритм <b><i>алгоритмом умной очереди</i></b>.  Вершины в <tex>F</tex> будут иметь точные метки. Если <tex>F</tex> непусто, мы удалим оттуда вершину и прорелаксируем всех её соседей. Если же <tex>F</tex> пусто, мы достанем из<tex>B</tex> вершину с минимальной меткой и прорелаксируем всех её соседей. Рассмотрим механизм релаксации: пусть мы уменьшаем <tex>d(u)</tex>. Заметим, что в этом случае <tex>u</tex> не могло лежать в <tex>F</tex>(иначе <tex>d(u)</tex> было не точно). Если <tex>u \in B</tex> - применим <tex>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>insert</tex>, и <tex>u</tex> запишется в<tex>F</tex> или <tex>B</tex>, в зависимости от того, выполняется ли условие леммы.