Algorithms for Searching the Shortest Path and Its Modification
Abstract
The article presents an overview of the main trends and methods of searching the shortest path information transmission in the telecommunications networks. The basic algorithms and their modifications are described. Special attention is given to the modified Dijkstra's algorithm that takes into account QoS requirements. The modified algorithm and its UML diagram are presented.
About the Authors
N. I. Listopad
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
I. A. Karuk
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
A. A. Hayder
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
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.
Review
For citations:
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.)
Views: 2069
Email this article 