Алгоритмы поиска кратчайшего пути и их модификация
Аннотация
В статье представлен обзор основных тенденций и методов поиска кратчайшего пути передачи информации в сетях телекоммуникаций. Описаны основные алгоритмы и их модификация. Особое внимание уделено модифицированному алгоритму Дейкстры, учитывающему при поиске кратчайшего пути требования QoS. Описан сам алгоритм и представлена его диаграмма классов.
Об авторах
Н. И. Листопад
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
д.т.н., профессор, заведующий кафедрой информационных радиотехнологий
Беларусь
д.т.н., профессор, заведующий кафедрой информационных радиотехнологий
И. А. Карук
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
магистрант
Беларусь
магистрант
А. А. Хайдер
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
аспирант
Список литературы
1. E.W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), P. 269-271.
2. Левитин А.В. // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: Вильямс, 2006. – С. 189-195, С. 349- 353.
3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. – 2-е изд. – М.: Вильямс, 2006. – С. 1296.
4. Электронный ресурс – Режим доступа: http://comp-science.narod.ru/KPG/BelmanFord.htm.
5. Рассел С., Норвиг П. Искусственный интеллект: современный подход (AIMA) = Artificial Intelligence: A Modern Approach (AIMA). – 2-е изд. – М.: Вильямс, 2007. – С. 1424.
6. Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 1-е изд. – М.: МЦНМО, 2004. — С. 523
7. Н. И. Листопад, Ю. И. Воротницкий, А. А.Хайдер // Оптимальная маршрутизация в мультисервисных сетях телекоммуникаций на основе модифицированного алгоритма Дейкстры. // Вестник БГУ, серия 1. – 2015. – № 1. – С.70-76.
Рецензия
Для цитирования:
Листопад Н.И., Карук И.А., Хайдер А.А. Алгоритмы поиска кратчайшего пути и их модификация. Информатизация образования. 2016;(1):48-63.
For citation:
Listopad N.I., Karuk I.A., Hayder A.A. Algorithms for Searching the Shortest Path and Its Modification. Informatization of Education. 2016;(1):48-63. (In Russ.)
Просмотров: 2067
Послать статью по эл. почте 