ГлавнаяАрхивАлгоритм поиска кратчайших путей для разреженных графов большой размерности

Алгоритм поиска кратчайших путей для разреженных графов большой размерности | Прикладная дискретная математика. 2013. № 1(19).

Рассматривается задача поиска кратчайших путей между всеми вершинами взвешенного ненаправленного разреженного графа. Предлагается алгоритм «разборки и сборки графа», использующий решение задачи на графе малой размерности для получения решения для исходного графа. Приводится сравнение предлагаемого алгоритма с одним из быстрых классических алгоритмов на данных из открытого доступа.
  • Title Алгоритм поиска кратчайших путей для разреженных графов большой размерности
  • Headline Алгоритм поиска кратчайших путей для разреженных графов большой размерности
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 1(19)
  • Date:
  • DOI
Ключевые слова
graph assembly, APSP, graph disassembly, разреженные графы, сжатие графа, сборка графа, разборка графа, APSP, задача о кратчайших путях, sparse graphs
Авторы
Ссылки
Ураков А. Р., Тимеряев Т. В. Использование особенностей взвешенных графов для более быстрого определения их характеристик // Прикладная дискретная математика. 2012. №2. C. 95-99.
http://www.dis.uniroma1.it/challenge9/download.shtml — 9th DIMACS Implementation Challenge — Shortest Paths (дата обращения: ноябрь 2012).
Geisberger R., Sanders P., et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks // International Workshop on Experimental Algorithms (WEA 2008). Provincetown: Springer, 2008. P. 319-333.
Johnson D. B. Efficient algorithms for shortest paths in sparse graph // J. ACM. 1977. No. 24. P. 1-13.
Dijkstra E. W. A note on two problems in connexion with graphs // Numer. Math. 1959. No. 1. P. 269-271.
Кормен Т. Х. и др. Алгоритмы: построение и анализ. М.: Вильямс, 2006. 1296 с.
Floyd R. W. Algorithm 97: Shortest Path // Comm. ACM. 1962. No 5(6). P. 345.
Bellman R. On a routing problem // Quarter. Appl. Math. 1958. No. 16. P. 87-90.
Алгоритм поиска кратчайших путей для разреженных графов большой размерности | Прикладная дискретная математика. 2013. № 1(19).
Алгоритм поиска кратчайших путей для разреженных графов большой размерности | Прикладная дискретная математика. 2013. № 1(19).
Полнотекстовая версия