ALCOMFT-TR-01-31

Daniele Frigioni, Alberto Marchetti-Spaccamela and Umberto Nanni
Fully Dynamic Shortest Paths in Digraphs with Arbitrary Arc Weights
Rome. Work packages 2 and 4. March 2001.

Abstract: We propose a new solution for the fully dynamic single source shortest paths problem in a directed graph G = (N, A) with arbitrary arc weights, that works for any digraph and has optimal space requirements and query time. If a negative-length cycle is introduced in the subgraph of G reachable from the source during an update operation, then it is detected by the algorithm. Zero-length cycles are explicitly handled. We evaluate the cost of the update operations as a function of a structural property of G and of the number of the output updates. We show that, if G has a k-bounded accounting function (as in the case of digraphs with genus, arboricity, degree, treewidth or pagenumber bounded by k), then the update procedures require O(min{m, k· n_A} · log n) worst case time for weight-decrease operations, and O(min{m · log n, k · (n_A + n_B)· log n + n}) worst case time for weight-increase operations. Here, n = |N|, m = |A|, n_A is the number of nodes affected by the input update, that is the nodes changing either the distance or the parent in the shortest paths tree, and n_B is the number of non affected nodes considered by the algorithm that also belong to zero-length cycles. If zero-length cycles are not allowed, then n_B is zero and the bound for weight-increase operations is O(min {m · log n, k· n_A · log n + n}). Similar amortized bounds hold if we perform also insertions and deletions of arcs.

Postscript file: ALCOMFT-TR-01-31.ps.gz (161 kb).