An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs

Andrzej Lingas, Mia Persson, Dzmitry Sledneu

A straightforward dynamic programming method for the single-source shortest paths problem (SSSP) in an edge-weighted directed acyclic graph (DAG) processes the vertices in a topolo…