On Fully Dynamic All Pairs Shortest Path in Sparse Digraphs
The All Pairs Shortest Path (APSP) problem is ubiquitous in computer science. The problem consists of finding for any vertex pair, the weighted shortest paths in a network with real-weighted edges. The problem has been studied thoroughly, both for dense graphs, where the number of edges can be quadratic in the number of vertices, and for sparse graphs, where the number of edges is considerably low
