Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights

We study the problem of maintaining the distances and the shortest paths from a source node in a directed graph with arbitrary arc weights, when weight updates of arcs are performed. We propose algorithms that work for any digraph and have optimal space requirements and query time. If a negative{length cycle is introduced during weight-decrease operations it is detected by the algorithms. The proposed algorithms explicitly deal with zero{length cycles. The cost of update operations depends on the class of the considered digraph and on the number of the output updates. We show that, if the digraph has a k-bounded accounting function (as in the case of digraphs with genus, arboricity, degree, treewidth or pagenumber bounded by k) the update procedures require O(k n log n) worst case time. In the case of digraphs with n nodes and m arcs k = O(sqrt{m}), and hence we obtain O(sqrt{m} n log n) worst case time per operation, which is better for a factor of O(sqrt{m}=log n) than recomputing everything from scratch after each input update. If we perform also insertions and deletions of arcs all the above bounds become amortized.