A new approach to dynamic all pairs shortest paths

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 Õ(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.

REFERENCES

• 1: Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Journal of Algorithms, v.12 n.4, p.615-638, Dec. 1991 [doi>10.1016/0196-6774(91)90036-X]
• 2: Surender Baswana , Ramesh Hariharan , Sandeep Sen, Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509928]
• 3: G. Italiano, Fully Dynamic All Pairs Shortest Paths with Real Edge Weights, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.260, October 14-17, 2001
• 4: Camil Demetrescu , Giuseppe F. Italiano, Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.633-643, July 08-13, 2002
• 5: E. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematik, 1:269--271, 1959.
• 6: S. Even and H. Gazit. Updating distances in dynamic graphs. Methods of Operations Research, 49:371--387, 1985.
• 7: J. Fakcharoenphol, Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.232, October 14-17, 2001
• 8: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 9: D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica, 22(3):250--274, 1998.
• 10: Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully dynamic algorithms for maintaining shortest paths trees, Journal of Algorithms, v.34 n.2, p.251-281, Feb. 2000 [doi>10.1006/jagm.1999.1048]
• 11: Donald E. Knuth , Daniel H. Greene, Mathematics for the Analysis of Algorithms, Birkhauser Boston, 1999
• 12: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 13: Valerie King, Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.81, October 17-18, 1999
• 14: P. Loubal. A network evaluation procedure. Highway Research Record 205, pages 96--109, 1967.
• 15: J. Murchland. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, London, UK, 1967.
• 16: G. Ramalingam , Thomas Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms, v.21 n.2, p.267-305, Sept. 1996 [doi>10.1006/jagm.1996.0046]
• 17: G. Ramalingam , Thomas Reps, On the computational complexity of dynamic graph problems, Theoretical Computer Science, v.158 n.1-2, p.233-277, May 20, 1996 [doi>10.1016/0304-3975(95)00079-8]
• 18: V. Rodionov. The parametric problem of shortest distances. U.S.S.R. Computational Math. and Math. Phys., 8(5):336--343, 1968.
• 19: Hans Rohnert, A Dynamization of the All Pairs Least Cost Path Problem, Proceedings of the 2nd Symposium of Theoretical Aspects of Computer Science, p.279-286, January 03-05, 1985

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
dynamic graph algorithms, shortest paths