Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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 |
irk-123456789-124702 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1247022017-10-03T03:02:42Z Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Васянин, В.А. Системный анализ Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию. Розглянуто алгоритм побудови найкоротших шляхів між усіма парами вузлів у неорієнтованій мережі за критерієм: мінімум дуг у шляху; мінімум довжини шляху. Проведено аналіз складності алгоритму та емпірично показано, що в міру зростання щільності мережі його обчислювальна ефективність стає на кілька порядків вищою, ніж у алгоритму Флойда, відповідно модифікованого для відшукання найкоротших шляхів за ступінчатим критерієм. 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. 2014 Article Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124702 519.168 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Васянин, В.А. Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Кибернетика и системный анализ |
| description |
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию. |
| format |
Article |
| author |
Васянин, В.А. |
| author_facet |
Васянин, В.А. |
| author_sort |
Васянин, В.А. |
| title |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_short |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_fullStr |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full_unstemmed |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_sort |
двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124702 |
| citation_txt |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT vasâninva dvuhkriterialʹnyjleksikografičeskijalgoritmpostroeniâvsehkratčajšihputejvseti |
| first_indexed |
2023-10-18T20:46:59Z |
| last_indexed |
2023-10-18T20:46:59Z |
| _version_ |
1796151096430821376 |