Shortest Paths in Planar Graphs with Real Lengths in O(n log~2 n/ log log n) Time

摘要

Given an n-vertex planar directed graph with real edge lengths and with no negative cycles, we show how to compute single-source shortest path distances in the graph in O(n log~2 n/ log log n) time with O(n) space. This improves on a recent O(n log~2 n) time bound by Klein et al.