An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic 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. Given 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 yielded by the shortest path from the source to v among th
