Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями

Пример приведен на рис. 1. Зная длину кратчайшего пути, можно эффективно вывести его полное описание при помощи итеративных поисков по таблице и заранее вычисленных представлений путей между транзитными вершинами. При условии, что вышеупомянутые наблюдения справедливы, а процент ложноположительных срабатываний мал, данный алгоритм работает очень эффективно, поскольку значительная часть всех запросов может быть обработана в строке 1, <math>d_{\mathcal{T}} (s, t)</math> может быть вычислено при помощи нескольких поисков в таблице, а источник и цельоставшихся запросов в строке 2 оказываются достаточно близки. И в самом деле, поиск ответов на оставшиеся запросы может быть ускорен за счет введения вторичного уровня маршрутизации транзитных узлов, основанного на множестве ''вторичных транзитных узлов'' <math>{\mathcal{T}}_2 \supset {\mathcal{T}}</math>. В данном случае нет необходимости в вычислении и хранении полной таблицы расстояний <math>{\mathcal{T}}_2 \times {\mathcal{T}}_2</math>, достаточно хранить только расстояния <math>\{d(u, v) | u, v \in {\mathcal{T}}_2 \and d(u, v) \ne d_{{\mathcal{T}}}(s, t) \}</math>, т. е. расстояния, которые не могут быть получены при помощи первичного уровня. Аналогичным образом можно добавить и более глубокие уровни.