An Algorithm for Finding Shortest Paths in a Maze
Boris V. Cherkassky · Optimization · 1986
This paper focuses on the problem of finding the shortest paths on a plane when the obstacle is a finite set of segments. The problem is reduced to finding the shortest paths in an equivalent network. The algorithm for constructing the equivalent network with running-time O(n 2logn), where nis the number of nodes in the network, is presented.