Incremental distance products via faulty shortest paths

Given a constant number d of n x n matrices with total m non-infinity entries, we show how to construct in (essentially optimal) (O) over tilde (mn + n(2)) time a data structure that can compute in (essentially optimal) (O) over tilde (n(2)) time the distance product of these matrices after incrementing the value (possibly to infinity) of a constant number k of entries. Our result is obtained by designing an oracle for single source replacement paths that is suited for short distances: Given a graph G = (V, E), a source vertex s, and a shortest paths tree T of depth d rooted at s, the oracle can be constructed in (O) over tilde (md(k)) time for any constant k. Then, given an arbitrary set S of at most k = O (1) edges and an arbitrary vertex t, the oracle in (O) over tilde (1) time either reports the length of the shortest s-to-t path in (V, E \ S) or otherwise reports that any such shortest path must use more than d edges. (C) 2020 Elsevier B.V. All rights reserved.