Geodesic
On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 2, pp. 177-181.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The Shoshan-Zwick algorithm solves the all-pairs shortest paths problem in undirected graphs with integer edge costs in the range $\{1, 2, \dots, M\}$. It runs in $\tilde{O}(M\cdot n^{\omega})$ time, where $n$ is the number of vertices, $M$ is the largest integer edge cost, and $\omega 2.3727$ is the exponent of matrix multiplication. It is the fastest known algorithm for this problem. This paper points out and corrects an error in the Shoshan-Zwick algorithm.
DOI : 10.7155/jgaa.00410
Keywords: Shoshan-Zwick algorithm, all-pairs shortest path, certification, matrix multiplication 
@article{JGAA_2017_21_2_a1,
     author = {Pavlos Eirinakis and Matthew Williamson and K. Subramani},
     title = {On the {Shoshan-Zwick} {Algorithm} for the {All-Pairs} {Shortest} {Path} {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {177--181},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2017},
     doi = {10.7155/jgaa.00410},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00410/}
}
TY  - JOUR
AU  - Pavlos Eirinakis
AU  - Matthew Williamson
AU  - K. Subramani
TI  - On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 177
EP  - 181
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00410/
DO  - 10.7155/jgaa.00410
LA  - en
ID  - JGAA_2017_21_2_a1
ER  - 
%0 Journal Article
%A Pavlos Eirinakis
%A Matthew Williamson
%A K. Subramani
%T On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem
%J Journal of Graph Algorithms and Applications
%D 2017
%P 177-181
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00410/
%R 10.7155/jgaa.00410
%G en
%F JGAA_2017_21_2_a1
Pavlos Eirinakis; Matthew Williamson; K. Subramani. On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 2, pp. 177-181. doi : 10.7155/jgaa.00410. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00410/

Cité par Sources :