A Branch-Checking Algorithm for All-Pairs Shortest Paths

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 $langle v, r_{1} , r_{2} , ldots , r_{k } = w rangle$ with $k $ arcs ($k geq 1$), is only then combined with an arc $(w,t) in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{ell } $--$ t$ path for each node $r_{ell}$ $(ell=k- 1 , k- 2, ldots, 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(n^{2})$. 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 $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.