Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2n)-time algorithm
Philip N. Klein, Shay Mozes, Oren Weimann · 2009
Abstract. We give an O(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires O(n log3 n) time and O(n logn) space. 1