Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
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| id |
nasplib_isofts_kiev_ua-123456789-124702 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| spellingShingle |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Васянин, В.А. Системный анализ |
| title_short |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_fullStr |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full_unstemmed |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_sort |
двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| author |
Васянин, В.А. |
| author_facet |
Васянин, В.А. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2014 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Двокритеріальний лексикографічній алгоритм побудови усіх найкоротших шляхів у мережі Two-criterion lexicographic algorithm of finding all shortest paths in networks |
| 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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124702 |
| citation_txt |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. |
| 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 |
| first_indexed |
2025-12-07T18:30:19Z |
| last_indexed |
2025-12-07T18:30:19Z |
| _version_ |
1850875281958502400 |