A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree

摘要

We consider a two-edge connected, non-negatively real-weighted graph G with n vertices and m edges, and a single-source shortest paths tree (SPT) of G rooted at an arbitrary vertex. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the vertices disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge. This allows to reduce consistently the set-up and computational costs which are incurred if one instead rebuilds a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the maximum or the average distance between the root and the disconnected vertices. For the former criteria, we present an time algorithm-where is the inverse of the Ackermann function-to find a best swap edge for every edge of the SPT, thus improving onto the previous time algorithm. Concerning the latter criteria, we provide an time algorithm for the special but important case where G is unweighted, which compares favourably with the time bound that one would get by using the fastest algorithm known for the weighted case-once this is suitably adapted to the unweighted case.