We formulate and study an algorithm for all-pairs shortest paths in a network with n nodes and m arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest v–w path, say ⟨v,r1, r2,…, rk = w⟩ with k arcs (k ≥ 1), is only then combined with an arc (w, t) ∈ A to update the distance label of pair v–t, if (w, t) is present on the shortest r𝓁–t path for each node r𝓁 (𝓁 = k-1,k-2,…,1). The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of O(n2). This way it can execute efficiently only the aforementioned distance updates, by picking the arcs (w, t) out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed nm0 (m0 being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies O(n2) distance updates, whereas known algorithms require Ω(n3) updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.
