Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети
|
|
| Creator |
Васянин, В.А.
|
|
| Subject |
Системный анализ
|
|
| Description |
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию.
Розглянуто алгоритм побудови найкоротших шляхів між усіма парами вузлів у неорієнтованій мережі за критерієм: мінімум дуг у шляху; мінімум довжини шляху. Проведено аналіз складності алгоритму та емпірично показано, що в міру зростання щільності мережі його обчислювальна ефективність стає на кілька порядків вищою, ніж у алгоритму Флойда, відповідно модифікованого для відшукання найкоротших шляхів за ступінчатим критерієм. 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. |
|
| Date |
2017-10-02T18:30:40Z
2017-10-02T18:30:40Z 2014 |
|
| Type |
Article
|
|
| Identifier |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос.
0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124702 519.168 |
|
| Language |
ru
|
|
| Relation |
Кибернетика и системный анализ
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|