Изменения

Для улучшения результата, нам необходимо сбалансировать прямой и обратный поиск.

[[Файл:reach3.jpg|right]]

* на начальном этапе <tex>\forall v: r(v)\leftarrow 0</tex>

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

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

[[Файл:reach5.jpg|right]]

[[Файл:reach6.jpg|right]]

Предыдущее улучшение создаёт проблему: мы должны предполагать, что кратчайший путь может начинаться в вершине с маленьким охватом, которые мы отбрасываем на каждой итерации. Для того, чтобы принять их во внимание, мы введём новую величину - <b>пенальти</b>(<i>penalty</i>) - верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.

* Чтобы определить высоту вершины, нам нужно понятие "ложных листьев". Для каждой вершины <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> (<i>shortcut</i>) - ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.