Перевод названия: Algorithm for optimal routing in multiservice networks
Тип публикации: статья из журнала
Год издания: 2018
Идентификатор DOI: 10.17223/2226308X/11/38
Ключевые слова: ресурсоограниченный кратчайший путь, графы большой размерности, resource constrained shortest path, big graph
Аннотация: Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути (RCSP) в графе G = (V,E). Задача RCSP является расширением известной задачи о кратчайшем пути в ориентированном графе, когда каждой дуге e £ E кроме основного веса w(e) дополнительно задаются несколько весовых функций wr (e), отражающих потребности в ресПоказать полностьюурсах, которые необходимы для передвижения по этой дуге. Задача RCSP позволяет моделировать мультисер-висные телекоммуникационные сети и определять в них оптимальный маршрут передачи данных между двумя заданными узлами сети. Предлагаются два алгоритма для приближённого решения задач RCSP на сетях большой размерности. Первый алгоритм является расширением известного алгоритма Дейкстры, который присваивает дополнительные метки каждой вершине. Эти метки позволяют алгоритму Дейкстры находить ресурсоограниченный путь в графе. В отличие от известных модификаций, такая модификация не требует дополнительных знаний о графе. Второй алгоритм, помимо дополнительных меток, добавляет к алгоритму Дейкстры потенциальные функции и ориентиры. Потенциальные функции, вычисленные на основе ориентиров, дают значительное ускорение на графах большой размерности. Предлагаемые алгоритмы не превосходят по вычислительной сложности алгоритм Дейкстры. Приводятся результаты вычислительных экспериментов, подтверждающие эффективность предложенных алгоритмов. The resource constrained shortest path problem (RCSP) is NP-hard extension of shortest path problem in the directed graph G = (V,E). In RCSP problem, each arc e E E has a cost w(e) and additional weight functions wr (e) which specify its requirements from a set of resource. Such problem allows to model a multi-service networks and search optimal route between two certain vertices. In this paper, we propose two heuristic algorithms for solving RCSP problem on big graphs. First algorithm is a modification of the famous Dijkstra's algorithm with additional labels, they allow to search the resource constrained shortest path. Unlike the known modifications, this modification does not require additional knowledge about the graph. Second algorithm adds potential functions and landmarks to the first. This modification accelerates algorithm on big graphs. Complexity of proposed algorithms corresponds to complexity of Dijkstra's algorithm. We provide computational experiments that show efficiency of proposed algorithms.
Журнал: Прикладная дискретная математика. Приложение
Выпуск журнала: № 11
Номера страниц: 122-127
ISSN журнала: 2226308X
Место издания: Томск
Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский государственный университет"