Geodesic
All-pairs shortest paths algorithm for high-dimensional sparse graphs
Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 84-92.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : APSP
Keywords: graph disassembly, graph assembly, sparse graphs. 
@article{PDM_2013_1_a6,
     author = {A. R. Urakov and T. V. Timeryaev},
     title = {All-pairs shortest paths algorithm for high-dimensional sparse graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {84--92},
     publisher = {mathdoc},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/}
}
TY  - JOUR
AU  - A. R. Urakov
AU  - T. V. Timeryaev
TI  - All-pairs shortest paths algorithm for high-dimensional sparse graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 84
EP  - 92
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/
LA  - ru
ID  - PDM_2013_1_a6
ER  - 
%0 Journal Article
%A A. R. Urakov
%A T. V. Timeryaev
%T All-pairs shortest paths algorithm for high-dimensional sparse graphs
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 84-92
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/
%G ru
%F PDM_2013_1_a6
A. R. Urakov; T. V. Timeryaev. All-pairs shortest paths algorithm for high-dimensional sparse graphs. Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 84-92. http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/

[1] Bellman R., “On a routing problem”, Quarter. Appl. Math., 1958, no. 16, 87–90 | MR | Zbl

[2] Floyd R. W., “Algorithm 97: Shortest Path”, Comm. ACM, 5:6 (1962), 345 | DOI

[3] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numer. Math., 1959, no. 1, 269–271 | DOI | MR | Zbl

[4] Kormen T. Kh. i dr., Algoritmy: postroenie i analiz, Vilyams, M., 2006, 1296 pp.

[5] Johnson D. B., “Efficient algorithms for shortest paths in sparse graph”, J. ACM, 1977, no. 24, 1–13 | DOI | MR | Zbl

[6] Geisberger R., Sanders P., et al., “Contraction hierarchies: faster and simpler hierarchical routing in road networks”, WEA 2008, International Workshop on Experimental Algorithms, Springer, Provincetown, 2008, 319–333

[7] 9th DIMACS Implementation Challenge — Shortest Paths, (data obrascheniya: noyabr 2012) http://www.dis.uniroma1.it/challenge9/download.shtml

[8] Urakov A. R., Timeryaev T. V., “Ispolzovanie osobennostei vzveshennykh grafov dlya bolee bystrogo opredeleniya ikh kharakteristik”, Prikladnaya diskretnaya matematika, 2012, no. 2, 95–99