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