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