# Finding the shortest path in a n-dimensional grid

I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at a time. Is there an algorithm for this or at least one I can refer to?

• Can you clarify: (a) what's a grid space? (b) By ordered pair, do you mean $n$-tuple?
– usul
Feb 28 '13 at 0:05
• This is not a research-level question. The shortest path from (a,b) to (c,d) walks east c-a steps and then walks north d-b steps. Feb 28 '13 at 0:54

It's easy: first get the 1st dimension right, then the 2nd dimension, then the 3rd dimension, etc.

For example, if you want to get from $(1,3,0)$ to $(3,4,1)$, you go via the following sequence of points: $(1,3,0), (2,3,0), (3,3,0), (3,4,0), (3,4,1)$.

Take a look at Floyd's algorithm. I would also suggest reading up on how to permute co-ordinates to generate Hamiltonian paths through n-dimensional space. Gray codes mutate one bit at a time and are related to the problem you state. As an aside, I don't understand how you can define a point in n-dimensional space with just a pair of co-ordinates, unless n=2.

Its the best you can do. Because its the minimum distance.

Its like driving taxicab in n-dimensional space.

$$d(P,Q) = \sum\limits_{i = 1}^{n} | P_i - Q_i|$$

P and Q are points in n-dimensional space and $P_i$ is gives $i^{th}$ co-ordinate of P.

It will take time linear in the distance between P and Q which is $d(P,Q)$.