Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log~2 n)-time algorithm

摘要

We give an O(n log~2 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.