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." />


Performance Comparison of Algorithms for the Dynamic Shortest Path Problem

Satoshi TAOKA  Daisuke TAKAFUJI  Takashi IGUCHI  Toshimasa WATANABE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.4   pp.847-856
Publication Date: 2007/04/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
networks,  shortest paths,  dynamic algorithms,  static algorithms,  computational experiments,  

Full Text: PDF(1.5MB)
>>Buy this Article


Summary: 
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.