An algorithm is described that solves the all pairs shortest path problem for a nonnegatively weighted directed graph of n vertices in average time \(O(n^ 2 \log n)\). The algorithm is a blend of two previous shortest path algorithms, those of G. B. Dantzig [Management Sci. 6, 187-190 (1960)] and P. M. Spira [SIAM J. Comput. 2, 28-32 (1973; Zbl 0243.05118)]. P. A. Bloniarz [ibid. 12, 588-600 (1983; Zbl 0521.68078)] categorized a class of random graphs called endpoint independent graphs; the new algorithm executes in the stated time on endpoint independent graphs and represents an asymptotic improvement over the \(O(n^ 2 \log n \log^* n)\) algorithm given by Bloniarz for this class of random graphs.