Ярлыки концентраторов - Hub labels

В информатике метки концентратора или алгоритм маркировки концентраторов это метод, который потребляет гораздо меньше ресурсов, чем Справочная таблица но по-прежнему очень быстро находит кратчайшие пути между узлами в графе, которые могут представлять, например, дорожные сети.^[1]

Этот метод позволяет не более двух операторов SELECT и анализа двух строк вычислить кратчайший путь между двумя вершинами графа. Для графа, ориентированного как дорожный граф, этот метод требует предварительного вычисления двух таблиц из структур построенный по методу иерархии сжатия. В конце концов, эти две вычисленные таблицы будут иметь столько же строк, сколько узлов присутствует в графе. Для каждой строки (каждого узла) будет рассчитана метка.

Метка - это строка, содержащая информацию о расстоянии между текущим узлом (узлом в строке) и всеми другими узлами, которые могут быть достигнуты при поиске по возрастанию в относительной многоуровневой структуре. Преимущество этих расстояний в том, что все они представляют собой кратчайшие пути.

Таким образом, для будущих запросов поиск кратчайшего пути будет начинаться от источника в первой таблице и пункта назначения во второй таблице, откуда будет выполняться поиск в метках общих узлов с соответствующей информацией о расстоянии. Только наименьшая сумма расстояний будет сохранена как результат кратчайшего пути.

Рекомендации