
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

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.E90A
No.4
pp.847856 Publication Date: 2007/04/01 Online ISSN: 17451337
DOI: 10.1093/ietfec/e90a.4.847 Print ISSN: 09168508 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>>
Summary:
An edgeweighted 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 ISIS, 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.

