Memory-Constrained Algorithms for Shortest Path Problem.
Tetsuo Asano, Benjamin Doerr · Max Planck Digital Library · 2011
We present an algorithm computing a shortest path between to vertices in a square grid graph with edge weights that uses memory less than linear in the number of vertices (apart from that for storing in the input). For any e > 0, our algorithm uses a work space of