Almost Optimal Multiple Source Shortest Paths and Reachability (opens in new tab)

Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\hat{O}(n^\omega) = O(n^{2.372})$ time [Seidel '95] providing significant savings over running $n$ SSSP instances...