Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/124702 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862721251515039744 |
|---|---|
| author | Васянин, В.А. |
| author_facet | Васянин, В.А. |
| citation_txt | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-07T18:30:19Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-124702 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:30:19Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Васянин, В.А. 2017-10-02T18:30:40Z 2017-10-02T18:30:40Z 2014 Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124702 519.168 Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию. Розглянуто алгоритм побудови найкоротших шляхів між усіма парами вузлів у неорієнтованій мережі за критерієм: мінімум дуг у шляху; мінімум довжини шляху. Проведено аналіз складності алгоритму та емпірично показано, що в міру зростання щільності мережі його обчислювальна ефективність стає на кілька порядків вищою, ніж у алгоритму Флойда, відповідно модифікованого для відшукання найкоротших шляхів за ступінчатим критерієм. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Двокритеріальний лексикографічній алгоритм побудови усіх найкоротших шляхів у мережі Two-criterion lexicographic algorithm of finding all shortest paths in networks Article published earlier |
| spellingShingle | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Васянин, В.А. Системный анализ |
| title | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_alt | Двокритеріальний лексикографічній алгоритм побудови усіх найкоротших шляхів у мережі Two-criterion lexicographic algorithm of finding all shortest paths in networks |
| title_full | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_fullStr | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full_unstemmed | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_short | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_sort | двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124702 |
| work_keys_str_mv | AT vasâninva dvuhkriterialʹnyileksikografičeskiialgoritmpostroeniâvsehkratčaišihputeivseti AT vasâninva dvokriteríalʹniileksikografíčníialgoritmpobudoviusíhnaikorotšihšlâhívumereží AT vasâninva twocriterionlexicographicalgorithmoffindingallshortestpathsinnetworks |