Two algorithms for shortest-paths problems in edge-weighted directed graphs

First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. For a positive integer parameter t , in O ( tm ) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that given by the shortest path from the source to v among the so called t + light paths . A directed path between two vertices is t + light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t = O ( n ) , our algorithm yields an O ( nm )-time solution to SSSP in directed graphs with real edge weights matching the time complexity of the Bellman-Ford algorithm. Our next contribution is a new algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input DAG. If the number of leaves is sufficiently small on the average, the algorithm is substantially faster than the best known algorithm in case of non-sparse DAGs. We also discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.