An algorithm for finding the number of shortest routes on square lattices

Abstract

Given an m×n square lattice. The number of shortest routes from lower left corner of the lattice to the upper right corner is (Formula presented.). Usually, when some line segments of the lattice are deleted, the number of shortest routes could be obtained by using inclusion-exclusion principle. However, when the number of deleted segments increases, the amount of calculation could be quite laborious. In this paper we propose a simple algorithm for obtaining the number of shortest routes that require much less calculation when the number of deleted segments increases. © 2007 Taylor & Francis Group, LLC.