Изменения

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

** найдём частичное частично обработанное дерево кратчайших путейиз <tex>v</tex>, чтобы найти вершины с охватом <tex>r(v) \geq \varepsilon</tex>

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

Пусть <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> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.

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