|
The ACM Journal of Experimental Algorithmics
|
Volume 8 Article 5, 2003
A Blocked All-Pairs Shortest-Paths Algorithm
by
Gayathri Venkataraman
and
and
Srabani Mukhopadhyaya
http://www.jea.acm.org/2003/VenkataramanBlocked/
Abstract:
We propose a blocked version of Floyd's all-pairs shortest-paths algorithm.
The blocked algorithm makes better utilization of cache than does Floyd's
original algorithm. Experiments indicate that the blocked algorithm
delivers a speedup (relative to the unblocked Floyd's algorithm) between
1.6 and 1.9 on a Sun Ultra Enterprise 4000/5000 for graphs that have
between 480 and 3200 vertices. The measured speedup on an SGI O2 for
graphs with between 240 and 1200
vertices is between 1.6 and 2.
Keywords: Algorithms, all pairs shortest pathds,
blocking, cache, speedup.
Categories: G.4 Mathematical Software: Algorithm Design and Analysis
- Sources:
Note that you must be a subscriber (institutional or individual) to
access these files.