Устойчивость решения в задаче о кратчайшем пути на графе

Изучается задача о кратчайшем пути между парой фиксированных вершин орграфа. Под устойчивостью решения понимается его “нечувствительность” к некоторым независимым аддитивным “возмущениям” весов ребер графа. Развивается подход, предложенный в [1]. Основное внимание уделяется изучению количественной характеристики – радиуса устойчивости, который является верхней гранью величин независимых возмущений весов ребер, не приводящих к появлению новых решений задачи. Приведена формула для радиуса устойчивости и исследована трудоемкость его поиска.