Faster Shortest-Path Algorithms for Planar Graphs

Citations Over TimeTop 10% of 1997 papers

Abstract

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.

Related Papers

• → An Algorithm of Shortest Path Based on Dijkstra for Huge Data(2009)53 cited
• → A New Shortest Path Algorithm based on Heuristic Strategy(2006)23 cited
• The Maximal Capacity of Directed Path Algorithm on Maximum Flow Network(2009)
• K Shortest Path Implementation(2013)