Программные продукты и системы

В представленной статье рассматривается проблема моделирования больших и сложных технических систем, а потому их графовая модель может быть довольно объемной по количеству вершин и связей и, кроме того, динамически изменяющейся во времени. Все это обосновано анализом существующих алгоритмов поиска кратчайших путей на больших и динамически изменяющихся графах.
В общем случае описанные в них подходы можно сформулировать так: большой граф случайным образом разбивается сначала на кластеры, потом в случае необходимости – на подкластеры, а затем выполняется перекомпоновка полученных кластеров (подкластеров) с учетом определенных требований, например, в зависимости от компоненты связности графа или других параметров. Вычисление кратчайших путей происходит внутри кластеров (подкластеров), а затем между ними, что приводит к получению итоговой матрицы расстояний. Однако предложенные подходы не учитывают разнотипные связи в GH-графах,  а также характеризуются избыточностью действий по перекомпоновке кластеров, что влечет за собой рост временных затрат на вычисления. Тем не менее подходы по разделению графа на части могут быть полезны в данном исследовании.
Подробное описание дается в статье "Модификация алгоритма поиска кратчайших путей GH-графа для анализа сложных технических систем", автор Зяблова Е.Р. (Южный федеральный университет, г. Таганрог).