Counting of Shortest Paths in a Cubic Grid

Abstract

The enumeration of shortest paths in cubic grid is presented herein, which could have importance in image processing and also in the network sciences. The cubic grid considers three neighborhoods — namely, 6-, 18- and 26-neighborhood related to face connectivity, edge connectivity and vertex connectivity, respectively. The formulation for distance metrics is given. L1, D18, and L∞ are the three metrics for 6-neighborhood, 18- neighborhood and 26-neighborhood. The task is to count the number of minimal paths, based on given neighborhood relations, from any given point to any other, in the three-dimensional cubic grid. Based on the coordinate triplets describing the grid, the formulations for the three neighborhoods are presented in this work. The problem both of theoretical importance and has several practical aspects.