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

doi:10.17223/2226308X/11/38

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

задача поиска кратчайшего пути | Дейкстры алгоритм

Add to "Quick Collection"

Description	Size	Format
Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях	546 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/2226308X/11/38

#задача поиска кратчайшего пути

#Дейкстры алгоритм

#телекоммуникационные сети

#графы большой размерности

Title: Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях
Creator: Солдатенко, Александр Александрович
Date: 2018
DOI: 10.17223/2226308X/11/38
Description: Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути (RCSP) в графе G = (V,E). Задача RCSP является расширением известной задачи о кратчайшем пути в ориентированном графе, когда каждой дуге e £ E кроме основного веса w(e) дополнительно задаются несколько весовых функций wr (e), отражающих потребности в ресурсах, которые необходимы для передвижения по этой дуге. Задача RCSP позволяет моделировать мультисервисные телекоммуникационные сети и определять в них оптимальный маршрут передачи данных между двумя заданными узлами сети. Предлагаются два алгоритма для приближённого решения задач RCSP на сетях большой размерности. Первый алгоритм является расширением известного алгоритма Дейкстры, который присваивает дополнительные метки каждой вершине. Эти метки позволяют алгоритму Дейкстры находить ресурсоограниченный путь в графе. В отличие от известных модификаций, такая модификация не требует дополнительных знаний о графе. Второй алгоритм, помимо дополнительных меток, добавляет к алгоритму Дейкстры потенциальные функции и ориентиры. Потенциальные функции, вычисленные на основе ориентиров, дают значительное ускорение на графах большой размерности. Предлагаемые алгоритмы не превосходят по вычислительной сложности алгоритм Дейкстры. Приводятся результаты вычислительных экспериментов, подтверждающие эффективность предложенных алгоритмов.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. Приложение. 2018. № 11. С. 122-127
Language: rus