Incremental algorithms for minimal length paths

We consider the problem of maintaining a solution to the All Pairs Shortest Paths Problem in a directed graph G = (V, E) where edges may be dynamically inserted. In case of unit edge costs, we introduce a new data structure which is able to answer queries concerning the length of the shortest path (i.e., a path with minimal number of edges) from one vertex to another in constant time, and to trace out the shortest path from one vertex to another in time linear in the number of edges reported. The total time required to maintain the data structure under a sequence of at most O(n2) insertions of edges is O(n3log n)lin the worst case, where n is the total number of vertices in G. Our data structure can be extended to provide incremental algorithms for maintaining maximal length paths or shortest paths when the edge costs are integers in a fixed range. All the given algorithms improve the best previously known bounds for the same problems and are a factor of log n away from the best possible bounds.