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