On the Dynamic Shortest Path Problem

This paper proposes an algorithm to solve the dynamic shortest path problem, which is to perform an arbitrary sequence of two kinds of operations on a directed graph with edges of equal length: the insert operation, which inserts an edge into the graph, and the FindShortest operation, which reports the shortest path between a pair of vertices if such a path exists. Each Find Shortest operation can be done in Ο(k) time, where k⩽n is the number of edges on the shortest path, and an arbitrary sequence of at most Ο(n^2) insert operations can be done in a worst-case time of Ο(n^3 1og n). Furtheremore, our algorithm can be extended to perform the cost-decreasing operation of the least-cost path problem, and always takes less time than previous algorithms.