Cascade Algorithm Revisited
Tadao Takaoka, Kiyomi Umehara · UC Research Repository (University of Canterbury) · 2014
We revisit the cascade algorithm for the all pairs shortest path (APSP) problem. The operation on the distace data is limited to the triple operation of min{a, b + c}. The best known complexity on this model is n 3 by Floyd’s algorithm. The cascade algorithm takes 2n 3 opearations. We first improve this bound to n 3 , that is, on a par with Floyd’s algorithm. Then we implement the improved version on a mesh computer and achieve 3n − 2 communication steps.