On the Number of Weighted Shortest Paths in the Square Grid

Abstract

In this paper the number of shortest paths between two points of the square grid using weighted distances is discussed. We use 8-adjacency square grid, that is, the weighted distance depends on the numbers and the weights of the horizontal, vertical and diagonal steps. Two types of neighborhood, and consequently two weights are used. As special cases, the Manhattan distance and chessboard distance, the two well-known and widely used digital distances of the two dimensional digital space occur. Despite our combinatorial result is theoretical, it is closely connected to applications, e.g., in communication networks. The number of shortest paths plays importance in applications of transmitting messages over networks, since they refer somehow to the width of the connection channel between the given points.