Studied in this interesting paper are fundamental problems that go back 45 years: in a graph G (n vertices, m edges) with positive edge weights, compute the distance to every vertex of G, from a selected single vertex (the generalized single source (GSS) problem), and from every vertex of G (the generalized all-pairs (GAP) problem.

This paper’s main contribution is in its demonstration of how to compute, in O(mn) time, a unique decomposition of G into r acyclic parts; thus, for example, if G is acyclic, r = 1. This decomposition can then be used to solve GSS in time O(m + r\log r) and GAP in time O(n(m + r\log r)). The decomposition depends on the determination of a trigger vertex for each of the r acyclic parts. This idea is extended to the determination of a feedback vertex set: a set of s vertices whose removal leaves an acyclic graph. The extension leads in turn to a new GAP algorithm requiring O(n(m + s^2)) time. The paper is well written, and ends with suggestions for further research.