We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with Õ(mn4/5) worst-case update time processing arbitrary $s,t$-distance queries in Õ(n4/5) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs.
No takes yet. Share an insight, caveat, or question.
Karczmarz et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: