Dijkstra’s algorithm solves the single-source shortest path problem on any directed graph in O(m + n log n) time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m is the number of edges in the graph. If the graph is nearly acyclic, other algorithms can achieve a time complexity lower than that of Dijkstra’s algorithm. Abuaiadh and Kingston gave a single source shortest path algorithm for nearly acyclic graphs with O(m + n log t) time complexity, where the new parameter, t, is the number of delete-min operations performed in priority queue manipulation. If the graph is nearly acyclic, then t is expected to be small, and the algorithm out-performs Dijkstra’s algorithm. Takaoka, using a different definition for acyclicity, gave an algorithm with O(m+n log k) time complexity. In this algorithm, the new parameter, k, is the maximum cardinality of the strongly connected components in the graph. The generalised single-source (GSS) problem allows an initial distance to be de- fined at each vertex in the graph. Decomposing a graph into r trees allows the GSS problem to be solved within O(m+r log r) time. This paper presents a new all-pairs algorithm with a time complexity of O(mn + nr log r), where r is the number of acyclic parts resulting when the graph is decomposed into acyclic parts. The acyclic decomposition used is set-wise unique and can be computed in O(mn) time. If the decomposition has been pre-calculated, then GSS can be solved within O(m+r log r) time whenever edge-costs in the graph change. A second new all-pairs algorithm is presented, with O(mn + nr2) worst case time complexity, where r is the number of vertices in a pre-calculated feedback vertex set for the nearly acyclic graph. For certain graphs, these new algorithms offer an improvement on the time complexity of the previous algorithms.