Сучасні модифікації алгоритму Дейкстри в комп’ютерних мережах

Abstract

У роботі розглядається алгоритм Дейкстри — класичний метод пошуку найкоротших шляхів у графах з невід’ємними вагами. Проаналізовано сучасні модифікації алгоритму, що застосовуються в оптичних, супутникових, центрових та високопродуктивних мережах. Показано, що різні варіанти алгоритму дозволяють у декілька разів підвищувати швидкість маршрутизації та ефективність використання мережевих ресурсів. Наведено порівняльну таблицю адаптацій Дейкстри та досліджено їх актуальність для сучасних інженерних задач.

The paper considers Dijkstra's algorithm, a classic method for finding the shortest paths in graphs with nonnegative weights. Modern modifications of the algorithm used in optical, satellite, centralised, and high-performance networks are analysed. It is shown that different variants of the algorithm allow to increase the routing speed and the efficiency of network resource utilisation several times over. A comparative table of Dijkstra's adaptations is provided and their relevance for modern engineering tasks is investigated.