Semi-dynamic shortest-path tree algorithms for directed graphs with arbitrary weights
share
Given a directed graph G with arbitrary real-valued weights, the single source shortest-path problem (SSSP) asks for, given a source s in G, finding a shortest path from s to each vertex v in G. A classical SSSP algorithm detects a negative cycle of G or constructs a shortest-path tree (SPT) rooted at s in O(mn) time, where m,n are the numbers of edges and vertices in G respectively. In many practical applications, new constraints come from time to time and we need to update the SPT frequently. Given an SPT T of G, suppose the weight on a certain edge is modified. We show by rigorous proof that the well-known Ball-String algorithm for positively weighted graphs can be adapted to solve the dynamic SPT problem for directed graphs with arbitrary weights. Let n_0 be the number of vertices that are affected (i.e., vertices that have different distances from s or different parents in the input and output SPTs) and m_0 the number of edges incident to an affected vertex. The adapted algorithms terminate in O(m_0+n_0 n_0) time, either detecting a negative cycle (only in the decremental case) or constructing a new SPT T' for the updated graph. We show by an example that the output SPT T' may have more than necessary edge changes to T. To remedy this, we give a general method for transforming T' into an SPT with minimal edge changes in time O(n_0) provided that G has no cycles with zero length.
READ FULL TEXT