Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях

Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути (RCSP) в графе $G=(V, E)$. Задача RCSP является расширением известной задачи о кратчайшем пути в ориентированном графе, когда каждой дуге $e\in E$ кроме основного веса $w(e)$ дополнительно задаются несколько весовых функций $w_r(e)$, отражающих потребности в ресурсах, которые необходимы для передвижения по этой дуге. Задача RCSP позволяет моделировать мультисервисные телекоммуникационные сети и определять в них оптимальный маршрут передачи данных между двумя заданными узлами сети. Предлагаются два алгоритма для приближённого решения задач RCSP на сетях большой размерности. Первый алгоритм является расширением известного алгоритма Дейкстры, который присваивает дополнительные метки каждой вершине. Эти метки позволяют алгоритму Дейкстры находить ресурсоограниченный путь в графе. В отличие от известных модификаций, такая модификация не требует дополнительных знаний о графе. Второй алгоритм, помимо дополнительных меток, добавляет к алгоритму Дейкстры потенциальные функции и ориентиры. Потенциальные функции, вычисленные на основе ориентиров, дают значительное ускорение на графах большой размерности. Предлагаемые алгоритмы не превосходят по вычислительной сложности алгоритм Дейкстры. Приводятся результаты вычислительных экспериментов, подтверждающие эффективность предложенных алгоритмов.