Given a directed graph @math with arbitrary real-valued weights, the single source shortest-path problem (SSSP) asks for, given a source @math in @math , finding a shortest path from @math to each vertex @math in @math . A classical SSSP algorithm detects a negative cycle of @math or constructs a shortest-path tree (SPT) rooted at @math in @math time, where @math are the numbers of edges and vertices in @math respectively. In many practical applications, new constraints come from time to time and we need to update the SPT frequently. Given an SPT @math of @math , 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 @math be the number of vertices that are affected (i.e., vertices that have different distances from @math or different parents in the input and output SPTs) and @math the number of edges incident to an affected vertex. The adapted algorithms terminate in @math time, either detecting a negative cycle (only in the decremental case) or constructing a new SPT @math for the updated graph. We show by an example that the output SPT @math may have more than necessary edge changes to @math . To remedy this, we give a general method for transforming @math into an SPT with minimal edge changes in time @math provided that @math has no cycles with zero length.
A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability.. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. Our algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.