Incremental single-source shortest paths in digraphs with arbitrary positive arc weights

Furthermore, this paper analyzes the expected update time of LSA dealing with edge weight increases or edge deletions in Erdös-Rényi (a.k.a., G(n,p)) random graphs. For weighted G(n,p) random graphs with arbitrary positive edge weights, LSA takes at most O(h(Ts)) expected update time to deal with a single edge weight increase as well as O(pn2h(Ts)) total update time, where h(Ts) is the height of input SSSP tree Ts. For G(n,p) random graphs, LSA takes O(ln⁡n) expected update time to handle a single edge deletion as well as O(pn2ln⁡n) total update time when 20ln⁡n/n≤p<2ln⁡n/n, and O(1) expected update time to handle a single edge deletion as well as O(pn2) total update time when p>2ln⁡n/n. Specifically, LSA takes the least total update time of O(nln⁡nh(Ts)) for weighted G(n,p) random graphs with p=cln⁡n/n,c>1 as well as O(n3/2(ln⁡n)1/2) for G(n,p) random graphs with p=cln⁡n/n,c>2.