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

Существуют две разных реализации: одна из них основана на простой геометрической решетке, а другая – на иерархии дорог, самом быстром из предыдущих подходов [5, 6]. Иерархия дорог состоит из последовательности уровней (рис. 1), где уровень i + 1 строится из уровня i путем обхода узлов низкой степени и удаления ребер, которые никогда не встречаются вдали от источника или цели кратчайшего пути. Любопытно, что эти уровни постепенно становятся геометрическим меньшими по размеру, во всех прочих отношениях они похожи друг на друга. Наивысший уровень содержит самые «важные» узлы и становится множеством первичных транзитных узлов. Узлы более низких уровней используются для формирования множеств транзитных узлов подчиненных уровней.