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.
shortest paths planar graphs algorithms theory monge replacement paths