Shortest paths in almost acyclic graphs

This paper presents an algorithm for the shortest-path problem on a directed graph having arbitrary arc weights. One feature of the algorithm is its ability to exploit a certain type of structure. Two examples of this feature are highlighted. The first example is when the given graph is ‘almost’ acyclic in the sense that there exists a small subset T of nodes, the deletion of which yields an acyclic graph. In this case, a version of the algorithm solves the shortest-path problem in O(|T|m) time; this bound is at least as good as the O(mn) time bound of Bellman. The second example is when the weight vector is ‘almost’ nonnegative in the sense that only a small subset F of arcs of the given graph have negative weight. In this case, the algorithm runs in O(min{|F|,n}(m + n log n)) time.