ALCOMFT-TR-02-92

C. Demetrescu and G.F. Italiano
A New Approach to Dynamic All Pairs Shortest Paths
Rome. Work package 4. May 2002.

Abstract: We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in ~O(n²) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic and uses simple data structures.

Postscript file: ALCOMFT-TR-02-92.ps.gz (124 kb).