Beyond Distance Ordering: Resource Complexity and Universal Optimality of Exact Labeled Directed Shortest Paths

Bin Cai

We study exact single-source shortest paths when the output is only the materialized labeled distance vector ($\mathrm{DIST}$), rather than a distance order. In the full determinis…