# ICS 269, Fall 2003: Theory Seminar

## 24 Oct 2003:

A new approach to dynamic all pairs shortest paths

authored by Camil Demetrescu and Giuseppe F. Italiano (STOC 2003, pp.159-166)

presented by Jonathan Sun

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*^{2}poly(log *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.