Діброва М. О. Спосіб багатошляхової маршрутизації в комп'ютерних мережах великої розмірності

Багатошляхова маршрутизація характеризується великою часовою складністю пошуку множини шляхів, що не перетинаються. Часова складність знаходження найкоротшого шляху по алгоритму Дейкстри представляє собою величину O(kN2). При знаходженні k-шляхів часова складність збільшується відповідно в k раз. В зв'язку з цим, для пошуку множини шляхів, що не перетинаються, в рамках цієї роботи був запропонований модифікований метод "гілок та границь". Це досягається за рахунок виключення операцій перебору варіантів формування кожного шляху. В процесі роботи алгоритму у відповідності з методом "гілок та границь" будується дерево рішень, коренем якого є початкова вершина, а листями є вершини, суміжні з кінцевою вершиною.