A survey of the all-pairs shortest paths problem and its variants in graphs

There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied, problems in (algorithmic) graph theory. In this paper, we survey the exact results of the static version of the all-pairs shortest paths problem and its variants namely, the Wiener index, the average distance, and the minimum average distance spanning tree (MAD tree in short) in graphs (focusing mainly on algorithmic results for such problems). Along the way we also mention some important open issues and further research directions in these areas.