An efficient multiple scanning order algorithm for accumulative least-cost surface calculation

The least-cost surface (LCS) calculation is a compute-intensive problem conventionally solved by the queue-based Dijkstra’s algorithm. Alternative raster-based scanning algorithms have also been proposed which use a moving window to scan the whole study area iteratively. Here we propose improvements to the raster-based algorithms. The main improvement is to implement multiple scanning orders (MSO) to replace the conventional single scanning order (SSO, typically from upper-left corner to lower-right corner, row by row). We compared the performance of different algorithms over different cost surfaces and with different numbers of source points. The comparison shows that a raster-based algorithm adopting MSO has a substantially better performance than a conventional raster-based algorithm using SSO. An MSO raster-based algorithm is generally comparable to the queue-based Dijkstra’s algorithm, and surpasses the latter over a relatively simple cost surface (e.g. in which the cost is resampled) and/or when the number of source points is relatively large. Our empirical experiments suggest that MSO reduces the time complexity from to (Formula presented.) to (Formula presented.) Additionally, we found that the MSO raster-based algorithm can be easily parallelized using shared-memory parallel programming.