Planar graphs, negative weight edges, shortest paths, and near linear time

摘要

In this paper, we present an O(nlog3n) time algorithm for finding shortest paths in an n-node planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by Lipton, Rose, and Tarjan in 1978 which runs in O(n3/2) time, and the best polynomial time algorithm developed by Henzinger, Klein, Subramanian, and Rao in 1994 which runs in O˜(n4/3) time. We also present significantly improved data structures for reporting distances between pairs of nodes and algorithms for updating the data structures when edge weights change.