How to calculate minimum required edges for all possible paths?

Question

I'm not a mathematician so please excuse me if I use the wrong vocabulary. This is not for any assignment or homework.

From point (0,0) to (4, -1) there are five possible 'taxi-cab' paths. Let n = sum of absolute difference between points, 5. Number of paths from either one to the other = (n * n-1) / 2 = 10. From one point to the other, half of that = 5.

But when I hand-draw this I count 13 'edges' (correct term?) between all the nodes or vertices(?) used. It's this number I'd like to calculate for any n-dimensional graph (up to 6-dimensions). How does one arrive at 13 from the vector (4, -1)?

Answer 1

If x-difference is dx, and y-difference is dy, then number of edges is

NE = dx*(dy+1) + dy*(dx+1)

(number of horizontal edges + number of vertical edges)

For your case dx=4, dy=1, and NE =4*2+5*1=13
For dx=4, dy=2 NE= 4*3+5*2=22

The same logic works for n-dimensional grids. For example, in 3D there are

dy*(dx+1)*(dz+1) vertical edges (along OY)
dx*(dy+1)*(dz+1) horizontal edges (along OX)
dz*(dx+1)*(dy+1) edges in depth (along OZ)

that gives 144 edges for 3x3x3 cube

Simple Python (suitable for any language) program to calculate this quantity for any dimension:

def numedges(dims:list):
    prod = 1
    for dim in dims:
        prod *= (dim + 1)
    ne = 0
    for dim in dims:
        ne += prod * dim // (dim+1)    #integer division
    return ne

print(numedges([2,4]))
print(numedges([3,3,3]))
print(numedges([2,3,4,5,6,7]))

>>>
22
144
96408

Using reduce:

from functools import reduce
def numedges(dims:list):
    product = reduce(lambda x,y: x*(y+1), dims, 1)
    return(reduce(lambda x,y: x+product*y//(y+1), dims, 0))