HomeIssuesAll-pairs shortest paths algorithm for highdimensional sparse graphs

All-pairs shortest paths algorithm for highdimensional sparse graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 1(19).

All-pairs shortest path problem on weighted undirected sparse graphs is considered. "Disassembly and assembly of graph" algorithm is proposed to obtain the solution of the problem for the given graph using the solution of the problem for a small-dimensional graph. The algorithm is compared with one of the fastest classic algorithms on public source data.
Download file
Counter downloads: 182
  • Title All-pairs shortest paths algorithm for highdimensional sparse graphs
  • Headline All-pairs shortest paths algorithm for highdimensional sparse graphs
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(19)
  • Date:
  • DOI
Keywords
graph assembly, APSP, graph disassembly, разреженные графы, сжатие графа, сборка графа, разборка графа, APSP, задача о кратчайших путях, sparse graphs
Authors
References
Ураков А. Р., Тимеряев Т. В. Использование особенностей взвешенных графов для более быстрого определения их характеристик // Прикладная дискретная математика. 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.
All-pairs shortest paths algorithm for highdimensional sparse graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 1(19).
All-pairs shortest paths algorithm for highdimensional sparse graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 1(19).
Download full-text version
Counter downloads: 231
Download file