Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети

• Published in: Кибернетика и системный анализ
• Date: 2014
• Main Author: Васянин, В.А.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2014
• Subjects: Системный анализ
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/124702
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос.

Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию. Розглянуто алгоритм побудови найкоротших шляхів між усіма парами вузлів у неорієнтованій мережі за критерієм: мінімум дуг у шляху; мінімум довжини шляху. Проведено аналіз складності алгоритму та емпірично показано, що в міру зростання щільності мережі його обчислювальна ефективність стає на кілька порядків вищою, ніж у алгоритму Флойда, відповідно модифікованого для відшукання найкоротших шляхів за ступінчатим критерієм. The algorithm of finding all shortest paths in undirected network is considered. Two criteria are used: the minimum number of arcs in the path and minimum path length. The algorithm is analyzed for complexity and it is empirically shown that as the network density increases, the computational efficiency of the proposed algorithm becomes higher than that of the Floyd algorithm adequately modified to find the shortest path by two criteria.