Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights

Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni

Abstract

We study the problem of maintaining the distances and the shortest paths from a source node in a directed graph with arbitrary arc weights, when weight updates of arcs are performed. We propose algorithms that work for any graph and require linear space and optimal query time. If a negative-length cycle is added during weight-decrease operations it is detected by the algorithms. The algorithms explicitly deal with zero-length cycles. We show that, if the graph has a k-bounded accounting function (as in the case of graphs with genus, arboricity, degree, treewidth or pagenumber bounded by k, and k-inductive graphs) the algorithms require O(k • n • log n) worst case time. In the case of graphs with n nodes and m arcs k = O \( \left( {\sqrt m } \right) \); this gives O(\( \left( {\sqrt m } \right) \) • n • log n) worst case time per operation, which is better for a factor of O(\( \left( {\sqrt m } \right) \)log n) than recomputing everything from scratch after each update.
BibTeX
@inproceedings{frigioni1998fully,
  author = {Daniele Frigioni and Alberto Marchetti-Spaccamela and Umberto Nanni},
  title = {{Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights}},
  booktitle = {ESA},
  year = {1998},
  doi = {10.1007/3-540-68530-8\_27},
}

Loading related content...

Figure