IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2007 · 14 citations · 0 references
ComputingComputer ScienceInformation TechnologyAlgorithmsComputer NetworksInterconnection NetworksAlgorithm AnalysisGraph AlgorithmsNetwork OptimizationRoutingRouting AlgorithmsShortest Path AlgorithmsDynamic Shortest PathsLink Layer ProtocolsLink-state RoutingShortest Path In Directed GraphsShortest Path ProblemsShortest Path Trees
An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence. As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.